너비 우선 탐색(BFS)

너비 우선 탐색(Breadth-First Search, BFS)은 그래프나 트리를 탐색하는 알고리즘 중 하나로, 시작 노드에서 시작해 인접한 노드를 먼저 탐색하는 방법이다. 이 방법은 '레벨 단위'로 탐색하는 것이 특징이며, 먼저 발견된 노드가 우선적으로 탐색된다.

BFS는 큐(Queue)를 사용하여 구현하는 것이 일반적이다. 시작 노드를 큐에 넣어 알고리즘이 시작되고, 큐에서 노드를 하나 꺼낸 후 그 노드의 인접 노드 중 아직 방문하지 않은 노드를 모두 큐에 넣는다. 이 과정을 큐가 빌 때까지 반복하게 되면 그래프의 모든 노드를 너비 우선으로 탐색할 수 있다.

BFS는 최단 경로를 찾는 문제나 두 노드 사이의 최단 거리를 찾는 문제에 주로 사용된다. 그러나 모든 간선의 가중치가 동일할 때만 최단 경로를 찾을 수 있다. 이 때문에 가중치가 있는 그래프에서 최단 경로 문제를 풀 때에는 다익스트라 알고리즘 등 다른 알고리즘이 사용된다.

예를 들어, 아래의 그래프가 있다고 가정하면,

  A
 / \\
B---C
|   |
D---E

BFS로 이 그래프를 A부터 탐색하면 다음과 같은 순서로 노드를 방문하게 된다: A, B, C, D, E. 이는 A에서 가장 가까운 B와 C를 먼저 방문하고, 그다음으로 B와 C에 인접한 D와 E를 방문하기 때문이다.

 

---

  1
 / \\
2   3
|   |
4   5

   1
 /   \
2   3
|     |
4   5

(아니.. 왜.. \가 한번 더 들어가는 것인가..?)

시작 노드를 1이라고 하면,

BFS 알고리즘은 다음과 같이 수행된다:

1. 시작 노드인 1을 큐에 넣고, 방문 처리를 한다. (큐: [1])
2. 큐에서 노드를 하나 꺼내어 (노드 1), 노드 1의 인접 노드인 2와 3을 큐에 넣고 방문 처리를 한다. (큐: [2, 3])
3. 다시 큐에서 노드를 하나 꺼내어 (노드 2), 노드 2의 인접 노드인 4를 큐에 넣고 방문 처리를 한다. (큐: [3, 4])
4. 큐에서 노드를 하나 꺼내어 (노드 3), 노드 3의 인접 노드인 5를 큐에 넣고 방문 처리를 한다. (큐: [4, 5])
5. 큐에 남아 있는 노드 4와 5를 차례로 꺼내면서, 각 노드의 인접 노드가 없으므로 큐에 노드를 추가하지 않는다. (큐: [])

따라서, 이 그래프의 BFS 탐색 결과는 "1 → 2 → 3 → 4 → 5"가 된다.

이처럼 BFS는 '레벨별로' 탐색하며, 현재 레벨에 있는 모든 노드를 방문하고 나서야 다음 레벨의 노드를 방문하게 된다. 이를 통해 시작 노드로부터의 최단 거리를 쉽게 계산할 수 있다.