0-1 BFS에서 visited만 쓰면 틀리는 이유: deque와 거리 갱신 실습

간선 비용이 0 또는 1이면, 먼저 발견한 경로가 항상 최소 비용인 것은 아닙니다. 일반 BFS의 ‘큐에 넣을 때 방문 처리’만 가져오면 나중에 찾은 더 싼 경로를 놓칠 수 있습니다. 0-1 BFS에서는 방문 여부 대신 현재까지의 최소 거리를 비교하고, 비용 0인 이동은 deque 앞에, 비용 1인 이동은 뒤에 넣습니다. 다섯 정점의 작은 그래프로 차이를 확인해 보겠습니다.

1. 간선 한 개가 두 개보다 비쌀 수 있습니다

다음 방향 그래프에서 출발점은 0입니다. 각 줄에 간선 비용을 적었으며, 반대 방향의 간선은 별도로 주어지지 않았습니다.

0 → 1: 비용 1
0 → 2: 비용 0
2 → 1: 비용 0
1 → 3: 비용 1
정점 4: 연결된 간선 없음

0에서 1로 직접 가면 비용이 1입니다. 하지만 0 → 2 → 1로 돌아가면 간선은 두 개를 지나도 총비용이 0입니다. 따라서 정점 1의 최단거리는 0이고, 정점 3까지의 최단거리는 1입니다.

정답을 정점 번호 순서로 적으면 [0, 0, 0, 1, None]입니다. None은 출발점에서 도달할 수 없다는 뜻이며, 비용 0과는 다른 상태입니다.

모든 간선 비용이 1인 일반 BFS는 간선 개수가 적은 경로부터 찾습니다. 이번 문제는 간선 개수가 아니라 비용의 합을 최소화해야 하므로 같은 방문 규칙을 그대로 사용할 수 없습니다.

2. 처음 큐에 넣었다는 이유로 거리를 확정하지 않습니다

0의 인접 간선을 적힌 순서대로 확인하면 정점 1을 비용 1로 먼저 발견합니다. 다음으로 정점 2를 비용 0으로 발견하고, 비용 0이므로 deque 앞에 넣습니다.

이때 정점 1을 이미 방문했다고 고정해 두면 문제가 생깁니다. 정점 2에서 1로 가는 비용 0의 간선을 보더라도 갱신을 막아 버리기 때문입니다.

같은 그래프에서 ‘처음 큐에 넣을 때 방문 처리하고 이후 갱신 금지’ 규칙을 적용하면 정점 1의 거리는 1에 머물고, 정점 3의 거리도 2가 됩니다. 덱의 앞뒤를 나누는 것만으로 이 오류가 해결되지는 않습니다.

대신 다음 후보 거리가 기존 거리보다 작은지 비교합니다.

후보 거리 = 현재 정점의 거리 + 간선 비용

처음 발견한 정점이거나 후보 거리가 더 작다면 거리를 바꾸고 덱에 넣습니다. 이것이 거리 갱신, 즉 완화입니다. ‘이미 본 정점인가’보다 ‘더 적은 비용으로 도착했는가’가 판단 기준입니다.

3. 비용 0은 앞에, 비용 1은 뒤에 넣습니다

현재 처리하는 거리보다 추가 비용이 없는 경로는 앞쪽에서 계속 처리합니다. 비용이 1 늘어나는 경로는 뒤쪽에서 기다리게 합니다. 0과 1만 있다는 조건 덕분에 덱의 앞뒤로 거리 처리 순서를 유지할 수 있습니다.

이번 구현은 정점 번호만 넣지 않고 (발견 당시 거리, 정점 번호)를 함께 보관합니다. 더 짧은 경로로 갱신되기 전에 들어간 옛 항목이 남아 있으면, 꺼낼 때 저장된 거리와 현재 dist를 비교해 건너뜁니다.

출발점 0을 처리한 뒤의 덱은 다음과 같습니다. 왼쪽이 먼저 꺼내는 쪽입니다.

[(0, 2), (1, 1)]

정점 2에서 정점 1까지 비용 0으로 갈 수 있으므로 정점 1을 거리 0으로 갱신하고 앞에 넣습니다.

[(0, 1), (1, 1)]

이후 (0, 1)을 처리하면 정점 3을 거리 1로 찾습니다. 나중에 (1, 1)을 꺼냈을 때는 정점 1의 현재 거리가 0이므로 오래된 항목으로 판단해 건너뜁니다.

이 검사는 정점을 처음 큐에 넣을 때 영구히 방문 처리하는 것과 다릅니다. 더 좋은 거리 후보를 받아들이되, 갱신 전의 낡은 작업을 반복하지 않기 위한 장치입니다.

4. Python으로 거리 갱신과 오래된 항목 건너뛰기를 구현합니다

아래 코드는 Python 3.10 이상에서 표준 라이브러리만 사용합니다. 정점 번호와 출발점은 정수이며, graph[u]에는 (도착 정점, 비용) 쌍을 넣습니다. 비용은 정수 0 또는 1로 주는 계약입니다.

from collections import deque

def zero_one_bfs(
    graph: list[list[tuple[int, int]]], start: int
) -> list[int | None]:
    n = len(graph)
    if not 0 <= start < n:
        raise ValueError("start is out of range")
    for edges in graph:
        for v, weight in edges:
            if not 0 <= v < n or weight not in (0, 1):
                raise ValueError("invalid vertex or weight")

    dist: list[int | None] = [None] * n
    dist[start] = 0
    queue = deque([(0, start)])

    while queue:
        current, u = queue.popleft()
        if current != dist[u]:
            continue
        for v, weight in graph[u]:
            candidate = current + weight
            if dist[v] is None or candidate < dist[v]:
                dist[v] = candidate
                item = (candidate, v)
                if weight == 0:
                    queue.appendleft(item)
                else:
                    queue.append(item)
    return dist

graph = [
    [(1, 1), (2, 0)],
    [(3, 1)],
    [(1, 0)],
    [],
    [],
]
distance = zero_one_bfs(graph, 0)
print(distance)
assert distance == [0, 0, 0, 1, None]

출력은 [0, 0, 0, 1, None]입니다. 정점 1이 처음에는 거리 1로 발견되더라도 최종 거리는 0으로 바뀝니다. 마지막 assert는 이 반례의 전체 거리 배열을 검사합니다.

입력 검사는 출발점·도착 정점의 범위와 0·1 이외의 비용을 살핍니다. 외부에서 문자열이나 구조가 다른 자료를 받는 API용 파서는 아니므로, 호출 전에 인접 리스트의 자료형을 계약에 맞춰 준비해야 합니다.

무방향 그래프라면 양쪽 인접 리스트에 간선을 넣습니다. 위 예제는 방향 그래프이므로 임의로 반대 간선을 추가하면 다른 문제를 계산하게 됩니다.

5. 0비용 순환에서는 같은 거리를 다시 넣지 않습니다

거리 갱신 조건은 candidate < dist[v]입니다. 이미 알려진 거리와 같은 후보를 다시 덱에 넣을 필요가 없습니다.

0 → 1과 1 → 0의 비용이 모두 0인 그래프를 생각하면 이유가 분명합니다. 같은 거리까지 갱신하는 <= 조건으로 바꾸면 0과 1이 서로를 계속 덱에 넣을 수 있습니다. 엄격히 더 짧아질 때만 갱신해야 불필요한 반복을 막습니다.

출발점에서 도달할 수 없는 정점은 끝까지 None으로 남습니다. 연결되지 않은 정점의 거리를 0으로 초기화하면 실제 0비용 경로와 구분할 수 없으므로 주의해야 합니다.

목표 정점을 처음 발견했다는 이유로 바로 종료하는 것도 피해야 합니다. 위 반례에서는 정점 1을 처음 찾은 비용이 정답이 아닙니다. 이 구현은 조기 종료 없이 도달 가능한 전체 거리를 계산합니다.

6. 시간 복잡도와 적용 범위를 확인합니다

덱에서 유효한 항목은 거리 순서에 맞춰 처리됩니다. 현재 거리 d에서 새 후보는 d 또는 d+1이므로, 비용 0은 앞에 넣고 비용 1은 뒤에 넣는 규칙으로 순서를 유지합니다. 이 규칙은 비용이 0과 1일 때의 구조를 이용하므로 다른 가중치에 그대로 옮길 수 없습니다.

이 성질을 이용하는 0-1 BFS의 시간 복잡도는 정점 수 V와 간선 수 E에 대해 O(V + E)입니다. 위 코드의 입력 검사와 거리 초기화도 이 범위에 포함됩니다. 오래된 항목은 인접 간선을 다시 훑지 않고 건너뜁니다.

거리 배열은 O(V)이며, 인접 리스트와 덱에 들어갈 후보까지 포함한 공간은 O(V + E)로 잡을 수 있습니다. 이는 구조에서 얻는 복잡도 설명이지 특정 컴퓨터에서 실행 시간을 측정한 수치는 아닙니다.

비용이 모두 1이면 일반 BFS가 더 단순합니다. 0과 1이 섞이면 0-1 BFS를 검토할 수 있고, 2 이상의 값을 포함하는 일반적인 음이 아닌 비용이라면 다익스트라 등 그 조건에 맞는 알고리즘이 필요합니다. 이 코드에서 비용 2를 비용 1처럼 뒤에 넣도록 바꾸는 것은 올바른 확장이 아닙니다.

핵심 요약

0-1 가중치에서는 먼저 발견한 경로보다 나중에 발견한 경로가 더 저렴할 수 있습니다. 첫 방문 여부만으로 거리 갱신을 막지 마세요.

더 짧은 거리일 때만 갱신하고, 비용 0은 덱 앞에, 비용 1은 뒤에 넣습니다. 저장 당시 거리와 현재 거리가 다른 항목은 건너뜁니다.

0비용 순환·도달 불가·방향 간선·가중치 범위를 작은 예제로 점검하세요. 간선 개수를 줄이는 문제와 비용 합을 줄이는 문제는 구분해야 합니다.