BFS visited를 언제 체크해야 하는지는 생각보다 자주 틀리는 부분입니다. 큐에 넣을 때 체크해도 되고 꺼낼 때 체크해도 비슷해 보이지만 결과는 달라질 수 있습니다.
일반적인 기준은 정점을 큐에 넣는 순간 visited를 체크하는 것입니다. 그래야 중복 enqueue를 줄이고 최단거리 기록도 자연스럽습니다.
BFS visited 처리 기준
BFS는 가까운 것부터 꺼내는 탐색이다
cp-algorithms의 BFS 설명처럼 BFS는 queue를 사용해 시작점에서 가까운 정점부터 탐색합니다.
큐에 넣을 때 체크하는 코드
from collections import deque
def bfs(start):
q = deque([start])
visited[start] = True
while q:
now = q.popleft()
for nxt in graph[now]:
if not visited[nxt]:
visited[nxt] = True
q.append(nxt)이 방식에서는 정점을 발견하는 순간 탐색 예약을 합니다. 그래서 다른 경로가 같은 정점을 다시 발견해도 큐에 또 넣지 않습니다.
꺼낼 때 체크하면 무엇이 문제일까
while q:
now = q.popleft()
if visited[now]:
continue
visited[now] = True
for nxt in graph[now]:
q.append(nxt)이 방식은 답이 맞는 경우도 있지만 같은 정점이 여러 번 큐에 들어갈 수 있습니다. 그래프가 커지면 큐 크기와 실행 시간이 불필요하게 늘어납니다.
상태 문제에서는 기준이 달라진다
visited가 단순 정점 번호가 아니라 (x, y, key_mask) 같은 상태라면 상태 전체를 기준으로 방문 여부를 봐야 합니다.
정리
대부분의 BFS에서는 큐에 넣을 때 visited를 체크하는 편이 좋습니다. visited는 방문 완료 표시라기보다 탐색 예약 표시로 보는 것이 더 정확합니다.
BFS visited를 늦게 체크하면 실제로 무엇이 늘어날까
작은 그래프에서는 방문 체크 위치가 달라도 결과가 비슷해 보일 수 있습니다. 하지만 간선이 많아지면 차이는 바로 큐 크기로 드러납니다. 꺼낼 때 visited를 체크하면 같은 정점이 여러 부모로부터 계속 큐에 들어갈 수 있습니다.
from collections import deque
graph = {
1: [2, 3],
2: [4],
3: [4],
4: []
}
# 4는 2에서도 들어오고 3에서도 들어올 수 있다.
# enqueue 시점에 visited를 찍으면 두 번째 삽입을 막을 수 있다.BFS의 핵심은 큐에 들어간 순간 “나중에 방문할 예정”이라는 점입니다. 따라서 visited는 실제 처리 완료 표시라기보다 탐색 예약 표시로 보는 편이 더 안전합니다.
최단거리 문제에서는 왜 더 중요할까
격자 최단거리, 미로 탐색, 숨바꼭질류 문제에서는 처음 어떤 칸이나 숫자에 도달한 순간의 거리가 최단거리입니다. BFS는 거리가 0, 1, 2, 3처럼 층 단위로 확장되기 때문입니다.
- 처음 큐에 넣는 순간 distance를 기록한다
- 이미 visited라면 더 긴 경로일 가능성이 높으므로 다시 넣지 않는다
- 꺼낼 때 distance를 갱신하면 같은 노드의 후보가 여러 번 생긴다
- 정답을 찾은 순간 종료해도 되는 문제는 enqueue/visited 기준이 더 중요해진다
visited가 위치만 보면 안 되는 경우
단, 모든 BFS에서 visited가 단순히 정점 번호나 좌표만 의미하는 것은 아닙니다. 열쇠를 가진 상태, 벽을 한 번 부순 상태, 남은 이동 횟수처럼 상태가 달라지면 같은 위치도 다른 노드가 됩니다.
# visited[x][y]만으로 부족한 경우
# 벽을 아직 부술 수 있는 상태와 이미 부순 상태는 다르다.
visited = [[[False] * 2 for _ in range(m)] for _ in range(n)]
# visited[x][y][broken]
# broken = 0: 아직 벽을 안 부숨
# broken = 1: 이미 벽을 부숨이런 문제에서 “큐에 넣을 때 visited” 원칙은 그대로 유지됩니다. 다만 visited의 차원이 문제 상태에 맞게 확장되어야 합니다.
디버깅할 때 확인할 질문
- 같은 좌표나 노드가 큐에 여러 번 들어가고 있지 않은가
- distance가 처음 발견 시점에 기록되는가
- visited가 위치만으로 충분한 문제인가, 상태까지 포함해야 하는가
- 정답을 찾고도 불필요하게 탐색을 계속하고 있지 않은가
관련해서 같이 보면 좋은 글
BFS 문제 풀이 패턴 정리도 함께 보면 이 글의 기준을 더 쉽게 연결할 수 있습니다.
BFS와 DFS 차이도 함께 보면 이 글의 기준을 더 쉽게 연결할 수 있습니다.
