> [!abstract] Introduction > 너비 우선 탐색(*Breadth-First Search*, BFS)은 시작 노드에서 가까운 노드부터 레벨 순서대로 탐색하는 그래프 탐색 알고리즘입니다. FIFO [[Queue]]를 사용하여 탐색 경계(*frontier*)를 관리하며, 모든 간선의 비용이 동일할 때 최단 경로를 보장합니다. [[Depth-First Search]]가 한 방향으로 끝까지 파고드는 것과 달리, BFS는 출발점에서 동심원을 그리듯 한 겹씩 바깥으로 확장합니다. 이 글에서는 BFS의 핵심 아이디어와 알고리즘, 시간·공간 복잡도, 최단 경로 보장 조건, 그리고 다른 탐색 알고리즘과의 관계를 살펴봅니다. ## 핵심 아이디어 BFS의 동작 원리는 단순하다. 시작 노드를 방문하고, 그 이웃을 모두 큐에 넣는다. 큐에서 노드를 하나씩 꺼내면서 아직 방문하지 않은 이웃을 다시 큐에 넣는다. [[Queue]]의 FIFO 특성 때문에, 시작 노드에서 거리 1인 노드를 모두 처리한 뒤에야 거리 2인 노드를 처리하게 된다. 이것이 BFS가 레벨 순서대로 탐색하는 이유다. ![[bfsTraversal.svg]] 위 그래프에서 노드 A부터 BFS를 수행하면, 먼저 A의 이웃인 B와 C를 방문하고, 그 다음에 B와 C의 이웃인 D, E, F를 방문한다. 탐색 순서는 A → B → C → D → E → F가 된다. ## 알고리즘 ``` function BFS(graph, start) returns visited order queue ← empty queue visited ← empty set visited.add(start) queue.enqueue(start) while queue is not empty do current ← queue.dequeue() for each neighbor of current do if neighbor not in visited then visited.add(neighbor) queue.enqueue(neighbor) ``` 핵심은 **발견 시점에 `visited`에 추가**한다는 것이다. 큐에서 꺼낼 때가 아니라 큐에 넣을 때 방문 처리를 해야 같은 노드가 큐에 중복으로 들어가는 것을 방지할 수 있다. ## 탐색 예시 아래 그래프에서 A를 시작으로 BFS를 수행하는 과정을 단계별로 살펴보자. 간선은 모두 비용 1의 무방향 간선이다. ``` A / \ B C / \ \ D E F ``` **Step 1** — A를 방문하고 큐에 넣는다. 큐: `[A]`. **Step 2** — A를 꺼내고 이웃 B, C를 방문 처리 후 큐에 넣는다. 큐: `[B, C]`. **Step 3** — B를 꺼내고 이웃 D, E를 방문 처리 후 큐에 넣는다. 큐: `[C, D, E]`. **Step 4** — C를 꺼내고 이웃 F를 방문 처리 후 큐에 넣는다. 큐: `[D, E, F]`. **Step 5** — D를 꺼낸다. 미방문 이웃이 없다. 큐: `[E, F]`. **Step 6** — E를 꺼낸다. 미방문 이웃이 없다. 큐: `[F]`. **Step 7** — F를 꺼낸다. 미방문 이웃이 없다. 큐: `[]`. 탐색 종료. 최종 방문 순서: A → B → C → D → E → F. 시작 노드로부터의 거리가 같은 노드들이 묶여서 처리되는 것을 확인할 수 있다 — 거리 0: {A}, 거리 1: {B, C}, 거리 2: {D, E, F}. ## Python 구현 ```python from collections import deque from typing import Optional def bfs( graph: dict[str, list[str]], start: str, goal: Optional[str] = None, ) -> list[str] | Optional[tuple[int, list[str]]]: """Breadth-First Search. Args: graph: 인접 리스트. {노드: [이웃, ...]}. start: 시작 노드. goal: 목표 노드 (None이면 전체 탐색). Returns: goal이 None이면 방문 순서 리스트. goal이 주어지면 (최단 거리, 경로) 또는 None. """ visited = {start} queue = deque([(start, [start])]) order = [] while queue: current, path = queue.popleft() order.append(current) if goal and current == goal: return len(path) - 1, path for neighbor in graph.get(current, []): if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) if goal: return None return order ``` `collections.deque`의 `popleft()`가 $O(1)$이므로, 리스트의 `pop(0)` ($O(n)$)을 사용하는 것보다 효율적이다. ## 시간 복잡도와 공간 복잡도 BFS는 모든 노드를 한 번씩, 모든 간선을 한 번씩(무방향이면 두 번씩) 탐색하므로 시간 복잡도는 $O(V + E)$이다. 여기서 $V$는 노드 수, $E$는 간선 수다. 공간 복잡도도 $O(V)$이다. 최악의 경우 한 레벨의 모든 노드가 큐에 들어갈 수 있으며, 이는 트리의 가장 넓은 레벨의 너비에 해당한다. 분기 계수(*branching factor*)가 $b$이고 최적 해의 깊이가 $d$일 때, 큐에 최대 $O(b^d)$개의 노드가 들어갈 수 있다. ## 최단 경로 보장 BFS가 최단 경로를 보장하는 것은 **모든 간선의 비용이 동일할 때**에 한한다. BFS는 시작 노드에서 $k$번 이동하여 도달할 수 있는 모든 노드를 $k+1$번 이동하여 도달할 수 있는 노드보다 먼저 탐색한다. 따라서 어떤 노드에 처음 도달했을 때의 경로가 곧 최단 경로가 된다. 간선 비용이 서로 다르면 이 보장이 깨진다. "한 번 이동"이 비용 1일 수도, 비용 100일 수도 있기 때문이다. 이 경우에는 [[Uniform-Cost Search]]나 [[A*]]처럼 누적 비용을 고려하는 알고리즘이 필요하다. ## BFS와 다른 알고리즘의 관계 BFS는 [[Best-First Search]] 프레임워크에서 $f(n) = \text{depth}(n)$으로 설정한 것으로 볼 수 있다. 모든 간선 비용이 1이면 $g(n) = \text{depth}(n)$이므로, 이 경우 BFS는 [[Uniform-Cost Search]]와 동일하게 동작한다. [[Depth-First Search]]는 BFS와 정반대로, [[Stack]](LIFO)을 사용하여 가장 깊은 노드부터 탐색한다. BFS는 최단 경로를 보장하지만 메모리 사용량이 크고, DFS는 메모리 효율이 좋지만 최단 경로를 보장하지 않는다. ## 어디에 쓰이는가 BFS는 비가중 그래프에서의 최단 경로 탐색에 가장 널리 쓰인다. 소셜 네트워크에서 두 사용자 간의 최소 연결 단계를 구하거나, 미로에서 최단 탈출 경로를 찾는 것이 대표적이다. 웹 크롤러가 링크를 따라가며 페이지를 수집하는 것도 BFS의 응용이며, 네트워크에서 브로드캐스트 메시지가 전파되는 방식 역시 BFS와 같은 패턴을 따른다. 트리에서의 레벨 순서 순회(*level-order traversal*)는 BFS 그 자체다. --- ## 출처 - Cormen, T. H. et al. (2022) *Introduction to Algorithms*. 4th edn. Cambridge, MA: MIT Press. Chapter 20.2. - Russell, S. and Norvig, P. (2021) *Artificial Intelligence: A Modern Approach*. 4th Global edn. Harlow: Pearson. Chapter 3.4.1.