큐와 너비 우선 탐색 BFS

가중치가 없는 지도에서 가장 적은 이동 횟수로 도착하는 길을 찾고 싶습니다. 목표는 큐의 FIFO 약속으로 왜 가까운 정점부터 처리하는지 설명하고 경로를 복원하는 것입니다. 그래프·스택·딕셔너리를 복습하세요.

개념과 약속

큐는 먼저 넣은 항목이 먼저 나오는 FIFO 구조입니다. collections.deque의 append는 뒤에 넣고 popleft는 앞에서 꺼냅니다. 리스트의 pop(0)처럼 나머지를 모두 밀지 않습니다. BFS는 시작 거리 0에서 이웃 거리 1, 그다음 거리 2를 차례로 발견합니다.

distance에 기록하는 순간 방문으로 표시하고 큐에 넣어 같은 정점을 중복 삽입하지 않습니다. parent에는 처음 발견하게 한 이전 정점을 기록합니다. 도착점에서 부모를 따라 출발점까지 거슬러 간 뒤 뒤집으면 경로가 됩니다. 도달하지 못한 정점은 사전에 없고 복원 결과는 빈 목록입니다. 모든 간선 비용이 같을 때만 이 거리를 비용 최소와 연결할 수 있습니다.

손으로 상태 추적하기

D의 부모는 B, B의 부모는 A입니다. 두 간선의 A→B→D를 얻습니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

from collections import deque

def bfs_distances(graph, start):
    if start not in graph:
        raise ValueError("start must be a vertex")
    distance, parent = {start: 0}, {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return distance, parent


def restore_path(parent, target):
    if target not in parent:
        return []
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]


graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
distance, parent = bfs_distances(graph, "A")
print(distance)
print(restore_path(parent, "D"))
print(restore_path(parent, "E"))

실행 결과:

{'A': 0, 'B': 1, 'C': 1, 'D': 2}
['A', 'B', 'D']
[]

왜 맞고 언제 끝나는가

큐에는 거리가 감소하지 않는 순서로 정점들이 들어갑니다. 거리 d의 정점에서 새 이웃을 발견하면 그 이웃의 거리는 d+1입니다. 그 이웃에 더 짧은 경로가 있었다면 더 앞선 거리 층에서 이미 발견했어야 하므로 첫 발견 거리가 최소입니다. 정점마다 큐에 한 번만 들어가 유한한 입력에서 끝납니다. parent의 거리는 매번 하나 줄어 복원도 종료합니다.

비용과 적용 범위

인접 목록 시간 O(V+E), 거리·부모·큐 공간 O(V)입니다. deque 양 끝 연산은 O(1)입니다. 경로 복원은 경로 길이에 비례합니다. 벽을 정점으로 넣지 않는 격자 미로도 같은 방식으로 표현할 수 있습니다.

스스로 풀어 보기

1. 위 그래프에 A—D를 추가하면 D의 거리와 부모는 무엇인가요?
2. 방문 표시를 큐에서 꺼낼 때로 미루면 이웃 B·C가 D를 각각 넣을 수 있나요?

힌트

1. A를 처리하면서 바로 D를 발견합니다.
2. 아직 꺼내지 않은 정점도 이미 큐에 있을 수 있습니다.

해설

1. 거리 1, 부모 A이고 경로는 A→D입니다.
2. 가능합니다. 첫 발견 때 기록하면 중복 후보와 부모 덮어쓰기를 피합니다. 꺼낼 때 표시하는 방식도 별도 설계할 수 있지만 이 코드의 증명과 비용을 그대로 붙이면 안 됩니다.

흔한 오해

가중치 100인 한 간선과 가중치 1인 두 간선이 있으면 BFS는 간선 수가 적은 쪽을 택할 수 있습니다. 비용 합이 최소인 문제에는 Dijkstra가 필요합니다.

복습과 다음 연결

Warshall은 모든 정점 쌍의 도달 여부를 표로 만듭니다. 큐 API는 deque 공식 문서를 참고하세요.