너비 우선 탐색: 고리로 탐색하기

"BFS 는 연못의 물결처럼 시작점에서 퍼져 — 두 걸음 떨어진 거 전에 한 걸음 떨어진 걸 다 끝내. 그 물결이 정확히 어떤 곳에 처음 닿을 때 최단 경로로 도착한 이유야."

알고리즘: 큐랑 visited 집합

너비 우선 탐색은 Stacks & Queues 트랙의 그 큐 기반 frontier 가, 이제 진짜 그래프 위에. 레시피:

시작 노드를 큐에 넣고 visited 표시.
노드 dequeue, 처리.
각 방문 안 한 이웃: visited 표시하고 enqueue.
큐가 빌 때까지 반복.

큐가 먼저 들어온 게 먼저 나가서, 늘 발견한 순서로 노드를 처리해 — 시작에서 거리순으로 엄격히: 한 걸음 떨어진 거 다, 그다음 두 걸음, 이런 식. frontier 가 고리로 확장돼.

왜 최단 경로를 찾나

그 고리별 확장이 BFS 의 초능력이야: BFS 가 어떤 노드든 처음 닿을 때, 가능한 최소 엣지 경로로 도착한 거야. 더 가까운 게 나중에 발견될 수 없어, BFS 가 바깥으로 가기 전에 각 거리 고리를 소진하니까. 그래서 가중치 없는 그래프에선, BFS 가 최단 경로를 공짜로 풀어 — 가면서 각 노드의 부모를 추적하면, target 에서 부모를 거슬러 걸어 실제 최단 경로를 재구성할 수 있어. "최소 이동", "가장 짧은 연결 사슬", "가장 가까운 매칭 노드" — 다 BFS.

BFS 는 큐 frontier 를 써, 시작에서 거리-고리로 확장해. 노드에 처음 닿는 게 최단 (최소-엣지) 경로를 통해서라, BFS 가 가중치 없는 최단 경로를 풀어. 늘 visited 집합을 들어 — 그래프는 순환이 있어.

다들 부딪히는 두 버그

첫째: visited 집합 잊기. 그래프는 순환이 있어, 그래서 visited 표시 안 하면 영원히 돌아 (또는 트리면 그냥 중복 일). 둘째, 더 미묘: dequeue 가 아니라 ENQUEUE 할 때 visited 표시. dequeue 까지 기다리면, 처리되기 전에 같은 노드가 다른 이웃들에 의해 큐에 여러 번 추가될 수 있어 — 큐를 부풀리고 가끔 거리를 망가뜨려. frontier 에 들어가는 순간 표시하면, 각 노드가 정확히 한 번 enqueue 돼. 이 두 습관이 BFS 를 O(V + E) 에 정확하게 만들어.

피파의 고백

내 첫 BFS 는 dequeue 할 때 노드를 visited 표시했고, 조밀 그래프에서 큐가 부풀었어 — 같은 노드가 다섯 번 앉아 있었어. 아빠의 고침은 한 줄 옮기기: enqueue 할 때 visited 표시. 갑자기 각 노드가 frontier 에 한 번 들어가고 전체가 깔끔한 O(V+E). 그래프 코드에선 visited 를 표시한다는 것만큼 언제 표시하냐가 중요하다는 걸 가르쳤어 — 우아함이랑 제곱의 차이인 한 줄 배치.

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 에서 각 노드까지 최단 거리를 나열해. 그다음 '소셜 네트워크에서 두 사용자 사이 최소 hop' 에 왜 (DFS 아니라) BFS 가 맞는 선택인지, 실제 경로를 반환하려면 어떤 추가 데이터를 추적할지 설명해.

Hint

dequeue 순서: A, B, C, D, E; 거리 A:0, B:1, C:1, D:2, E:3. BFS 는 거리순 탐색이라 처음 도착이 최소 hop; DFS 는 더 긴 길로 D 에 먼저 닿을 수 있어. 노드당 부모 포인터를 추적해 거슬러 걸어 경로 재구성.

알고리즘: 큐랑 visited 집합

왜 최단 경로를 찾나

다들 부딪히는 두 버그

피파의 고백

Code

External links

Exercise

Progress

댓글 0