BFS — 너비 우선 탐색 알고리즘 설명

너비 우선 탐색, 즉 BFS는 시작 노드로부터의 거리가 가까운 순서대로 노드를 방문하는 그래프 알고리즘입니다. 먼저 간선 하나 거리의 모든 노드를 확인한 뒤, 간선 두 개 거리의 노드로 이동하고, 그다음 세 개 거리의 노드로 계속 나아갑니다.

이처럼 층별로 진행되는 순서가 핵심 아이디어입니다. 그래프가 비가중치이거나 모든 간선의 비용이 같다면, BFS는 시작 노드에서 도달 가능한 모든 노드까지의 최단 경로 길이도 구해 줍니다.

너비 우선 탐색이 하는 일

BFS는 **큐(queue)**를 사용합니다. 큐는 먼저 들어온 것이 먼저 나가는 자료구조입니다. 이 큐가 층별 순서를 유지해 주며, 먼저 발견된 노드가 먼저 처리됩니다.

일반적인 흐름은 다음과 같습니다:

• 시작 노드를 방문 처리한다
• 그 노드를 큐에 넣는다
• 큐의 맨 앞 노드를 꺼낸다
• 아직 방문하지 않은 각 이웃 노드를 큐의 뒤에 넣는다
• 큐가 빌 때까지 반복한다

각 노드의 부모 노드도 함께 저장하면, 탐색이 끝난 뒤 하나의 최단 경로를 복원할 수 있습니다.

큐가 층을 만드는 이유

노드 $A$가 시작점이라고 가정해 봅시다. $A$와 직접 연결된 이웃들은 $A$로부터 거리 $1$이므로 먼저 큐에 들어갑니다. 그리고 그 노드들이 처리된 뒤에야 그들의 미방문 이웃이 큐에 들어가므로, 다음 물결은 거리 $2$가 됩니다.

이것이 BFS가 시작점으로부터의 거리에 따라 노드를 자연스럽게 묶는 이유입니다. BFS는 어떤 경로가 짧을지 추정하지 않습니다. 큐가 더 긴 경로를 보기 전에, 간선 수가 더 적은 모든 경로를 먼저 끝내도록 강제합니다.

BFS 예시: 간선 수로 최단 경로 찾기

다음 그래프를 사용해 봅시다:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

$A$에서 시작하면 큐는 다음과 같이 바뀝니다:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

이것이 의미하는 바는 다음과 같습니다:

먼저 $A$를 처리한 뒤 $B$와 $C$를 추가합니다. 다음으로 $B$, 그다음 $C$를 처리하면서 $D$와 $E$가 추가됩니다. 그 후 $D$와 $E$를 처리하면 $F$에 도달합니다.

따라서 BFS의 방문 순서는 다음과 같습니다:

$$A,\ B,\ C,\ D,\ E,\ F$$

$A$로부터의 거리는 다음과 같습니다:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

이 예시는 BFS의 핵심 장점을 보여 줍니다. BFS는 거리 $3$에서 $F$에 도달하므로, $A$에서 $F$까지의 최단 경로는 간선 $3$개를 사용합니다. 하나의 최단 경로는 $A \to B \to D \to F$입니다. 또 다른 최단 경로는 $A \to C \to E \to F$입니다.

BFS에서 자주 하는 실수

BFS가 항상 가장 비용이 낮은 경로를 찾는다고 가정하기

이 말은 모든 간선의 비용이 같거나 그래프를 비가중치로 볼 때만 맞습니다. 간선마다 가중치가 다르면, BFS는 간선 수는 더 적지만 총비용은 더 큰 경로를 찾을 수 있습니다.

노드를 너무 늦게 방문 처리하기

표준 BFS에서는 보통 노드를 큐에 넣는 순간 방문 처리하지, 나중에 큐에서 꺼낼 때 처리하지 않습니다. 이렇게 해야 같은 노드가 큐에 여러 번 들어가는 일을 막을 수 있습니다.

BFS와 DFS를 혼동하기

BFS는 층별로 탐색합니다. 깊이 우선 탐색인 DFS는 한 갈래를 끝까지 따라간 뒤에 되돌아옵니다. 두 알고리즘은 서로 다른 종류의 문제에 강합니다.

방문 순서가 이웃의 나열 순서에 따라 달라질 수 있다는 점을 잊기

같은 층 안에서의 정확한 방문 순서는 이웃이 어떤 순서로 나열되어 있는지에 따라 달라질 수 있습니다. 거리 보장은 그대로 유지되지만, 순회 순서는 달라질 수 있습니다.

너비 우선 탐색은 언제 사용될까

BFS는 도달 가능성, 트리의 레벨 순회, 또는 간선 수로 측정한 최단 경로 길이가 중요할 때 유용합니다.

또한 각 이동의 비용이 같은 상태 공간 문제에서도 자주 등장합니다. 이 조건에서는 BFS가 최소 이동 횟수를 찾는 가장 명확한 방법인 경우가 많습니다.

BFS를 쉽게 기억하는 방법

BFS를 시작 노드에서 바깥으로 퍼져 나가는 물결이라고 생각해 보세요. 물결이 한 번 퍼질 때마다 거리가 간선 하나씩 늘어납니다.

직접 해 보려면 작은 그래프를 하나 그리고, 시작 노드를 정한 뒤, 각 단계가 끝날 때마다 큐의 상태를 적어 보세요. 다음 단계로 나아가고 싶다면 비슷한 그래프 순회 문제를 풀어 보고, 그래프에 가중치가 있을 때도 최단 경로에 대한 주장이 여전히 성립하는지 확인해 보세요.