너비 우선 탐색(BFS) 쉽게 이해하기: 동작 원리, 코드, 시간 복잡도

BFS가 해결하는 문제

겉으로는 그래프가 아니지만 사실 그래프인 문제가 많습니다. 웹 페이지와 링크, 소셜 네트워크의 친구 관계, 게임 판의 칸, 퍼즐의 상태가 그렇습니다. BFS는 이런 그래프에 대해 두 가지 질문에 답합니다. 시작 노드에서 어떤 노드에 도달할 수 있는가, 그리고 각 노드까지 가장 적은 단계로 가려면 몇 단계가 필요한가입니다.

BFS는 거리가 늘어나는 순서대로 동심원을 그리듯 탐색하므로, 어떤 노드에 처음 도달했을 때의 경로는 항상 간선 수가 가장 적은 경로입니다. 그래서 모든 간선의 비용이 같을 때 최단 경로를 구하는 표준 알고리즘으로 쓰입니다.

핵심 아이디어

1. 시작 노드를 큐에 넣고 방문 처리합니다.
2. 큐의 맨 앞에 있는 노드를 꺼냅니다.
3. 아직 방문하지 않은 이웃 노드마다 방문 처리를 하고 큐의 맨 뒤에 넣습니다.
4. 큐가 빌 때까지 2번과 3번을 반복합니다.

노드는 큐에서 꺼낼 때가 아니라 큐에 넣을 때 방문 처리해야 합니다. 그렇지 않으면 같은 노드가 처리되기 전에 여러 번 큐에 들어갈 수 있습니다.

단계별 예제

다음 무방향 그래프를 생각해 봅시다. A–B, A–C, B–D, C–D, C–E, D–F. A에서 시작하고 이웃은 알파벳 순서로 방문합니다.

방문 순서는 A, B, C, D, E, F입니다. D는 B와 C 양쪽에서 도달할 수 있지만, B에서 처음 발견되는 순간 방문 처리되므로 한 번만 발견됩니다.

파이썬 구현

큐에는 collections.deque를 사용합니다. popleft()는 O(1)이지만 list.pop(0)은 O(n)입니다. 그래프는 각 노드를 이웃 노드의 리스트에 대응시키는 딕셔너리(인접 리스트)로 표현합니다.

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

여기서 dist 딕셔너리는 방문 집합이자 결과 저장소 역할을 함께 합니다. 실제 경로를 복원하려면 각 노드의 부모도 저장해 두었다가 목표 노드에서 거꾸로 따라가면 됩니다.

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

시간 복잡도와 공간 복잡도

V는 정점(노드)의 수, E는 간선의 수입니다. 리스트 대신 인접 행렬을 쓰면 한 노드의 이웃을 찾는 데 O(V)가 들기 때문에 시간 복잡도가 O(V²)이 됩니다.

변형과 흔한 실수

• 격자 BFS: 각 칸을 노드로, 상하좌우 네 칸(또는 대각선 포함 여덟 칸)을 간선으로 봅니다. 칸을 추가하기 전에 범위와 벽을 확인해야 합니다.
• 다중 시작점 BFS: 여러 시작 노드를 거리 0으로 큐에 한꺼번에 넣습니다. 미로에서 가장 가까운 출구처럼 가장 가까운 시작점까지의 거리를 구할 때 쓰입니다.
• 0-1 BFS: 간선 가중치가 0 또는 1뿐이면 덱을 사용하고 가중치 0인 이웃은 앞쪽에 넣습니다. O(V + E)에 최단 경로를 구할 수 있습니다.
• 양방향 BFS: 시작점과 목표점에서 동시에 탐색하다가 두 탐색 경계가 만나면 멈춥니다. 탐색하는 노드 수가 훨씬 줄어드는 경우가 많습니다.
• 레벨 단위 처리: 매 라운드 시작 시 len(queue)를 기록해 두고 정확히 그만큼의 노드만 꺼내면 한 번에 한 레벨씩 처리할 수 있습니다.

BFS를 쓰는 경우와 실제 활용

• 코딩 인터뷰 문제: 미로나 격자의 최단 경로, 단어 사다리, 썩은 오렌지(다중 시작점 BFS), 이진 트리 레벨 순서 순회, 나이트의 최소 이동 횟수.
• 네트워크: k홉 이내의 모든 기기 찾기, P2P 네트워크의 브로드캐스트, 소셜 그래프에서 거리 2의 "알 수도 있는 사람".
• 시드 페이지로부터의 링크 거리 순서대로 페이지를 방문하는 웹 크롤러.
• 가비지 컬렉터(예: 체니의 복사 수집기)와 최소 이동 횟수가 필요한 퍼즐 풀이기.