0-1 BFS를 이해하려면 먼저 최단 경로의 후보를 거리순으로 꺼내야 한다는 Dijkstra의 핵심을 잡아야 합니다. 덱은 정점 방문 순서를 임의로 바꾸는 요령이 아니라, 간선 비용이 0과 1뿐이라는 전제 아래 다음 후보의 거리 차이가 한 단계뿐임을 이용한 자료구조입니다. 그러므로 정점의 최초 발견과 최단 거리 확정은 서로 다른 사건입니다.
이동 횟수와 경로 비용
S→A 비용이 1이고 S→B와 B→A 비용이 모두 0이라고 합시다. 일반 BFS는 간선 하나로 A를 먼저 발견하지만 최저 비용은 B를 거치는 0입니다. 처음 발견한 거리를 고정하는 규칙을 그대로 쓰면 안 됩니다.
모든 간선 비용이 0 또는 1이라면 일반 최소 힙보다 단순한 덱으로 후보 순서를 유지할 수 있습니다. 이를 0-1 BFS라고 부릅니다. 단위 비용 BFS와 달리 더 낮은 거리를 발견하면 갱신해야 합니다.
0 비용 후보와 덱 전단 처리
일반 BFS의 큐는 먼저 발견한 정점부터 처리합니다. 하지만 비용이 0인 이동을 발견했다면 이야기가 달라집니다. 그 이동은 한 칸을 더 가도 비용이 늘지 않으므로, 이미 기다리는 비용 1짜리 경로보다 먼저 살펴봐야 합니다.
이때 앞뒤 양쪽에서 넣고 뺄 수 있는 덱(deque)을 사용합니다. 현재까지 비용이 d인 정점에서 출발하면 새 후보의 비용은 둘 중 하나입니다.
- 비용 0인 간선을 지나면 여전히 d입니다. 덱 앞에 넣어 먼저 처리합니다.
- 비용 1인 간선을 지나면 d+1입니다. 덱 뒤에 넣어 현재 비용의 후보들이 끝난 뒤 처리합니다.
Dijkstra처럼 매번 모든 후보 중 최솟값을 찾고 싶은데, 새 비용이 두 종류뿐이라 힙 대신 덱의 앞뒤만 사용해 순서를 유지할 수 있는 것입니다.
그림을 글로 읽기
- S · 거리 0
- B · 거리 0
- A · 1에서 0으로 개선
- S · 거리 0 → B · 거리 0: 0
- S · 거리 0 → A · 1에서 0으로 개선: 1
- B · 거리 0 → A · 1에서 0으로 개선: 0
| 단계 | 덱 앞→뒤, (거리,정점) | 동작 |
|---|---|---|
| 시작 | [(0,S)] | S 등록 |
| S 확장 | [(0,B),(1,A)] | A는 뒤, B는 앞 |
| B 확장 | [(0,A),(1,A)] | A를 0으로 개선해 앞에 등록 |
| A 확장 | [(1,A)] | 최저 비용 확정 |
| 옛 A 추출 | [] | 현재 거리와 달라 건너뜀 |
오래된 후보와 유효 거리 확정 상태
상태를 손으로 추적할 때는 “덱에 들어간 snapshot”과 “현재 dist”를 함께 적습니다. S에서 A가 (1,A)로 들어간 뒤 B를 통해 (0,A)가 추가되면, 두 항목이 모두 남아 있어도 (0,A)만 유효합니다. 예상 결과는 A의 parent가 B로 남고, 옛 (1,A)는 추출 즉시 건너뛰는 것입니다.
zeroOneBfs(graph, source):
validate_all_vertices_and_weights_in({0,1})
dist[*] = INF
parent[*] = NONE
settled = empty set
dist[source] = 0
q = deque([(0,source)])
while q not empty:
d,u = q.pop_front()
if d != dist[u] or u in settled: continue
settled.add(u)
for v,w in outgoing(u):
candidate = d+w
if candidate < dist[v]:
dist[v] = candidate
parent[v] = u
if w == 0: q.push_front((candidate,v))
else: q.push_back((candidate,v))
return dist,parent
위 코드에서는 덱에 정점 번호만 넣지 않고 그 정점을 넣을 당시의 거리도 함께 저장합니다. 표의 A처럼 처음에는 거리 1로 들어갔다가 나중에 거리 0으로 개선될 수 있기 때문입니다. 옛 항목 (1,A)를 꺼냈을 때 현재 dist[A]가 0이면, 이미 더 좋은 경로가 있으므로 그 항목은 버립니다.
settled는 처음 발견했다는 표시가 아니라, 유효한 최소 거리로 꺼내 이웃까지 처리했다는 표시입니다. 이 두 시점을 구분해야 앞의 반례를 올바르게 풉니다.
탐색 중 그래프는 바뀌지 않고, 모든 비용은 0 또는 1이어야 합니다. 거리의 정수 덧셈도 표현 범위를 넘지 않아야 합니다. 도달하지 못한 정점은 INF로 남기고, 시작 정점 자체가 없다면 입력 오류로 처리합니다.
현재 유효한 최소 거리 d의 정점을 꺼냈다고 하겠습니다. 비용 0 간선으로 만든 후보는 여전히 d이므로 덱 앞에 넣어 같은 층의 다른 후보보다 먼저 처리하고, 비용 1 간선으로 만든 후보는 d+1이므로 덱 뒤에 둡니다. 예제에서 S를 처리한 뒤 B는 앞, A는 뒤에 놓이고, B를 처리하면서 거리 0의 A가 다시 앞에 들어옵니다. 이 규칙이 반복되면 유효한 항목은 거리순으로 처리되므로 Dijkstra처럼 pop 순간을 확정 시점으로 삼을 수 있습니다. 처음 덱에 넣을 때가 아니라 snapshot이 현재 dist와 맞는 항목을 꺼냈을 때만 settled로 표시합니다.
시간·공간 복잡도와 입력 전제
실무에서는 간선 가중치를 읽는 경로에서 0·1 외 값이 섞이는지 먼저 진단하고, 섞이면 Dijkstra나 다른 알고리즘으로 선택을 바꿉니다. 작은 그래프에서 같은 입력을 기준 Dijkstra와 비교해 거리 배열이 같고, <=를 쓴 변형에서는 0 사이클이 재등록을 늘리는지 확인하면 덱 순서와 엄격한 완화의 역할을 분리해 볼 수 있습니다.
각 정점은 유효 확장 한 번, 각 간선은 그 확장에서 한 번 검사합니다. 성공적인 완화와 덱 삽입은 O(E) 이내이고 push·pop이 O(1)이므로 시간은 O(V+E)입니다. 이 snapshot·지연 삭제 구현의 덱에는 중복 항목이 남을 수 있어 전체 보조 공간 상한은 O(V+E)로 볼 수 있습니다. 단순 방문 배열 하나만 두는 BFS의 공간 설명을 그대로 가져오지 않습니다.
비용이 2나 음수가 들어오면 이 두 층의 덱 불변식이 깨집니다. 목표를 조기 반환하는 변형에서도 아직 탐색하지 않은 잘못된 간선을 놓치지 않으려면 입력 전제 또는 전체 사전 검증이 필요합니다.
0 비용 사이클과 엄격한 거리 개선
0 비용 사이클에서도 candidate < dist[v]인 경우만 넣으면 같은 거리로 무한히 재등록하지 않습니다. <=로 바꾸면 동점 사이클에서 후보가 계속 생길 수 있습니다. 경로 부모도 엄격한 개선 때만 갱신하고 복원 시 실제 간선 비용 합을 확인합니다.
작은 0·1 그래프에서 모든 시작점의 거리를 기준 Dijkstra와 비교합니다. 직접 비용 1과 우회 비용 0, 고립 정점, 자기 간선, 평행 간선과 0 사이클을 포함합니다. 덱을 쓴다는 사실보다 최소 거리의 순서가 왜 유지되는지 설명할 수 있어야 합니다.