너비 우선 탐색: 물결처럼 퍼져 나가기

"BFS는 연못에 이는 물결처럼 시작점에서 퍼져 나가. 두 걸음 떨어진 곳으로 가기 전에 한 걸음 떨어진 곳을 전부 끝내지. 그 물결이 어떤 자리에 처음 닿는 순간이 곧 최단 경로인 이유가 여기 있어."

알고리즘: 큐와 방문 집합

너비 우선 탐색은 스택과 큐 트랙에서 본 그 큐 기반 경계를 이제 진짜 그래프 위에 올린 거야. 순서는 이래.

시작 노드를 큐에 넣고 방문 표시를 해.
노드를 하나 꺼내서 처리해.
아직 방문하지 않은 이웃마다 방문 표시를 하고 큐에 넣어.
큐가 빌 때까지 반복해.

큐가 먼저 들어온 걸 먼저 내보내니까 언제나 발견한 순서대로 노드를 처리해. 시작점에서의 거리 순으로 엄격하게 말이야. 한 걸음 떨어진 노드를 전부 보고, 그다음 두 걸음, 이런 식이지. 경계가 동심원처럼 넓어지는 거야.

왜 최단 경로를 찾을까

이 한 겹씩 퍼지는 방식이 BFS의 초능력이야. BFS가 어떤 노드에 처음 닿는 순간, 그건 가능한 가장 적은 간선으로 도착한 거야. 더 가까운 경로가 나중에 발견될 수가 없거든. BFS는 바깥으로 나가기 전에 각 거리의 노드를 전부 소진하니까. 그래서 가중치 없는 그래프에서는 BFS가 최단 경로를 공짜로 풀어줘. 가면서 각 노드의 부모를 기록해 두면 목표 지점에서 부모를 거슬러 올라가 실제 최단 경로까지 복원할 수 있고. "최소 이동 횟수", "가장 짧은 연결 고리", "가장 가까운 조건 만족 노드"는 전부 BFS야.

BFS는 큐로 경계를 관리하면서 시작점에서 거리 순으로 한 겹씩 퍼져 나가. 어떤 노드에 처음 닿는 게 곧 간선 수가 가장 적은 경로라서, BFS가 가중치 없는 최단 경로를 풀어. 그리고 방문 집합은 반드시 들고 다녀. 그래프에는 순환이 있으니까.

다들 부딪히는 두 가지 버그

첫째, 순환이 있거나 여러 경로가 있는 그래프에서는 방문 관리가 반드시 필요해. 둘째, 보통의 단일 출발 BFS는 enqueue하는 시점에 발견 표시를 해서 같은 노드가 큐에 여러 번 들어가는 걸 막아. dequeue할 때까지 미루면 중복해서 큐에 쌓이니 시간과 메모리가 늘고, 부모를 덮어쓰는 구현이라면 경로 기록까지 흐트러질 수 있어. 다만 그렇다고 거리 값 자체가 언제나 틀린다고 일반화하진 마. 어떤 불변식을 쓰느냐에 따라 늦게 표시해도 답은 맞을 수 있어. 비효율적일 뿐이지.

피파의 고백

내가 처음 짠 BFS는 dequeue할 때 방문 표시를 했는데, 조밀한 그래프에서 큐가 부풀어 올랐어. 같은 노드가 다섯 번씩 들어앉아 있더라. 아빠의 수정은 줄 하나를 옮기는 거였어. enqueue할 때 방문 표시를 하는 것. 그러니까 각 노드가 경계에 한 번씩만 들어가고 전체가 깔끔한 O(V+E)가 됐지. 그래프 코드에서는 방문 표시를 한다는 사실만큼이나 언제 하느냐가 중요하다는 걸 그때 배웠어. 줄 하나의 위치가 우아함과 제곱 복잡도를 가르더라.

Code

부모를 기록해 경로까지 복원하는 BFS 최단 경로·python

from collections import deque

graph = {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
    "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],
}

def bfs_shortest(graph, start, goal):
    """가중치 없는 그래프의 최단 경로 (최소 엣지). O(V + E)."""
    visited = {start}                  # ENQUEUE 시점에 표시
    parent = {start: None}             # 경로 재구성용
    q = deque([start])
    while q:
        node = q.popleft()             # FIFO -> 거리순 탐색
        if node == goal:
            break
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)        # 다시-큐 되기 전에 지금 표시
                parent[nb] = node
                q.append(nb)
    # goal 에서 부모를 거슬러 걸어 경로 재구성
    if goal not in parent: return None
    path, cur = [], goal
    while cur is not None:
        path.append(cur); cur = parent[cur]
    return path[::-1]

print(bfs_shortest(graph, "A", "F"))   # ['A', 'C', 'F'] — 엣지 2개, 최단

Exercise

그래프 A–B, A–C, B–D, C–D, D–E에서 A부터 BFS를 손으로 돌려 봐. 노드가 dequeue되는 순서와 A에서 각 노드까지의 최단 거리를 적어. 그다음 '소셜 네트워크에서 두 사용자가 최소 몇 단계로 이어지는가'에 왜 DFS가 아니라 BFS가 맞는 선택인지, 그리고 실제 경로까지 돌려주려면 무슨 데이터를 더 기록해야 하는지 설명해.

Hint

dequeue 순서는 A, B, C, D, E야. 거리는 A가 0, B와 C가 1, D가 2, E가 3이고. BFS는 거리 순으로 훑으니까 처음 도착하는 게 곧 최소 단계야. DFS는 더 긴 길로 D에 먼저 닿을 수도 있고. 실제 경로를 돌려주려면 노드마다 부모 포인터를 기록해 뒀다가 거슬러 올라가면 돼.

알고리즘: 큐와 방문 집합

왜 최단 경로를 찾을까

다들 부딪히는 두 가지 버그

피파의 고백

Code

External links

Exercise

Progress

댓글 0