0-1 BFS는 간선 가중치가 0 또는 1뿐인 그래프에서 최단거리를 구하는 알고리즘입니다. 일반 BFS처럼 큐를 쓰지만, 정확히는 deque를 사용해 0 비용 이동은 앞에, 1 비용 이동은 뒤에 넣습니다.
핵심은 우선순위 큐를 쓰지 않아도 deque 안의 거리 순서를 유지할 수 있다는 점입니다. 이 조건은 모든 간선 가중치가 0 또는 1일 때만 성립합니다.
일반 BFS로는 왜 부족할까
일반 BFS는 모든 간선 비용이 같을 때 최단거리를 보장합니다. 한 칸 이동이 항상 비용 1이라면 먼저 도착한 경로가 최단거리입니다.
하지만 어떤 이동은 비용 0이고 어떤 이동은 비용 1이라면, 간선 개수가 적은 경로가 비용도 작다고 말할 수 없습니다. 이때 일반 BFS의 visited 처리만으로는 최단 비용을 보장하기 어렵습니다.
다익스트라를 쓰면 안 될까
다익스트라를 쓰면 됩니다. 가중치가 음수가 아니기 때문에 0과 1 가중치 그래프도 다익스트라로 풀 수 있습니다. 다만 가중치가 0 또는 1로 제한되어 있다면 우선순위 큐보다 더 단순한 deque로 같은 순서를 유지할 수 있습니다.
deque를 쓰는 이유
현재 거리 d인 정점에서 나가는 간선의 가중치는 0 또는 1입니다. 따라서 새로 발견되는 거리는 d 또는 d+1뿐입니다. 큐 안의 거리 차이가 크게 벌어지지 않으므로, 0 비용은 앞에 넣고 1 비용은 뒤에 넣으면 작은 거리부터 처리하는 순서가 유지됩니다.
from collections import deque
INF = 10**18
dist = [INF] * n
dist[start] = 0
dq = deque([start])
while dq:
v = dq.popleft()
for to, weight in graph[v]:
if dist[v] + weight < dist[to]:
dist[to] = dist[v] + weight
if weight == 0:
dq.appendleft(to)
else:
dq.append(to)0이면 앞, 1이면 뒤
가중치 0인 간선을 타면 거리가 늘지 않습니다. 그래서 지금 처리 중인 거리와 같은 우선순위를 가져야 하므로 deque 앞에 넣습니다. 가중치 1인 간선을 타면 거리가 1 늘어나므로 뒤에 넣습니다.
visited를 바로 쓰면 위험한 이유
0-1 BFS에서는 일반 BFS처럼 처음 방문했다고 끝내면 안 되는 경우가 있습니다. 더 작은 비용으로 다시 갱신될 가능성을 dist 배열로 확인해야 합니다. 그래서 핵심 조건은 visited가 아니라 ‘더 짧은 거리로 갱신되는가’입니다.
언제 0-1 BFS를 의심해야 할까
- 간선 비용이 0 또는 1로만 나온다
- 방향 전환은 비용 1, 같은 방향 이동은 비용 0처럼 조건부 비용이 있다
- 벽을 부수는 횟수, 방향 변경 횟수처럼 횟수를 최소화한다
- 우선순위 큐로 풀 수 있지만 가중치 종류가 두 개뿐이다
다익스트라와 비교
- 다익스트라: 비음수 가중치 일반 최단거리
- 0-1 BFS: 가중치가 0과 1일 때 특화
- 다익스트라: 우선순위 큐 사용
- 0-1 BFS: deque 사용
- 다익스트라: 보통 O(E log V)
- 0-1 BFS: 조건이 맞으면 O(E)
정리
0-1 BFS는 다익스트라의 특수한 경우로 보면 이해하기 쉽습니다. 가중치가 0과 1뿐이라면 우선순위 큐 대신 deque로 거리 순서를 유지할 수 있습니다.
알고리즘의 근거와 구현은 CP-Algorithms 0-1 BFS 문서를 참고할 수 있습니다. 기본 BFS 감각은 BFS visited 처리 글과 함께 보면 더 탄탄해집니다.
