[C++] 넓이 우선 탐색 (BFS)

프로그래밍에서 탐색 (Searching)과 순회 (Traversal)는 매우 중요한 개념이다. 그래프나 트리 같은 구조를 다룰 때는 특정한 규칙을 따라 데이터를 탐색해야 하며, 그중 너비 우선 탐색 (Breadth-First Search, BFS)은 깊이 우선 탐색 (DFS)과 함께 가장 널리 사용되는 탐색 방법 중 하나이다.

---

이번 글에서는 BFS가 무엇이고, 어느 때 사용하는지 정리하며, 큐 (Queue) 자료구조를 활용한 BFS의 구현 방법을 정리한다.

너비 우선 탐색이란?

너비 우선 탐색 (BFS)은 그래프의 한 정점에서 시작하여 인접한 정점들을 먼저 모두 탐색한 후, 그다음 인접한 정점들을 탐색하는 방식으로 진행된다. 즉, 특정 노드에서 가까운 노드를 먼저 방문한 후 점점 멀리 있는 노드를 방문하는 방식이다. BFS의 탐색 순서는 선입선출 (FIFO, First-In-First-Out) 구조를 따르는 큐를 활용하여 구현할 수 있다.

 

BFS는 보통 최단 경로를 찾거나 최적의 해를 보장해야 하는 문제에서 유용하게 사용된다. 탐색 시작 노드와 가까운 노드를 우선 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다. 이는 특정 노드에서 목표 노드까지 도달하는 경로를 찾을 때, 가장 적은 이동 횟수를 보장하는 특징을 갖기 때문이다.

이전에도 다루었던 위의 그래프에서, BFS를 이용하면 DFS와는 다른 결과가 나온다.

1번에서 시작하면 2-3-5-6-4, 또는 3-2-4-6-5가 된다.

 

DFS 때와 마찬가지로 초기 세팅부터 그림으로 정리해보면 아래와 같다.

BFS 초기세팅. DFS와 같은 구성인데 스택 대신 큐를 사용한다.

시작하면서 1을 방문한 것과 같으므로 방문 여부 체크에 True로 설정되어 있는 것을 확인할 수 있다.

다음으로는 스택에 있는 1을 빼고 1의 인접 노드 2와 3을 스택에 쌓는 작업이다.

큐에 있던 1이 빠지고 2와 3이 들어왔다.

그리고 FIFO 규칙에 맞게 2가 나가고 2의 인접노드 중 아직 방문하지 않은 5와 6이 들어온다.

다음으로는 3이 빠지고, 그러면서 4가 큐로 들어오게 될 것이다.

그 다음에 있는 5가 빠지면서 큐에 새롭게 추가되는 노드는 없고 6과 4에 대해서도 마찬가지로 그냥 빠져나가게 된다.

DFS와 마찬가지로 큐에 원소가 없을 때까지 계속 원소를 제거하는 (pop())과정을 반복한다.

BFS 구현 방법

임의의 노드를 시작점으로 잡았을 때의 결과를 보여주기 위해 for문을 이용했다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for (int i = 0; i < graph[node].size(); i++) {
            int next = graph[node][i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int n = 6;
    graph.resize(n);
    visited.resize(n, false);
    
    // 그래프 예시
    graph[0] = {1, 2};
    graph[1] = {0, 4, 5};
    graph[2] = {0, 3};
    graph[3] = {2, 5};
    graph[4] = {1};
    graph[5] = {1, 3};
    
    for (int i = 0; i < n; i++){
        bfs(i);
        cout << endl;
        visited.clear();
        visited.resize(n, false);
    }
    return 0;
}

인접노드를 집어넣는 순서는 DFS와 같다고 하더라도, 빼내는 순서가 다르기 때문에 (LIFO와 FIFO의 차이), DFS 글에서의 코드와 결과에서 많은 차이가 있는 것을 볼 수 있을 것이다.

BFS의 장단점

최단경로를 찾는 데에는 DFS에 비해 더 유리해보이나, 절대적으로 좋은 것은 아니다.

장점

• 최단 경로 보장: 같은 가중치를 갖는 그래프에서 최단 경로를 보장한다.
• 무한 루프에 빠질 가능성이 적음: 방문 처리를 제대로 하면 DFS보다 무한 루프에 빠질 가능성이 낮다.
• 최적의 해를 찾는 문제에 적합: BFS는 너비를 우선 탐색하기 때문에 항상 최적의 해를 찾을 수 있다.

단점

• 메모리 사용량이 큼: 큐에 저장해야 하는 노드가 많아질 경우, 많은 메모리를 필요로 한다.
• 경로 탐색이 DFS보다 느릴 수 있음: DFS는 특정 경로를 깊게 탐색하면서 빠르게 종료될 수 있지만, BFS는 너비 우선 탐색이므로 시간이 더 걸릴 수 있다.

이 외에도 그래프의 노드가 가중치를 갖거나 하면 BFS만으로는 풀기 어려운 문제도 있다.

---

BFS는 DFS와 함께 탐색 알고리즘의 기본이 되는 방법이다. 깊이 우선 탐색이 후입선출 (LIFO) 방식으로 작동한다면, 너비 우선 탐색은 선입선출 (FIFO) 방식으로 동작한다. 각각의 알고리즘은 문제의 성격에 따라 적절하게 선택하여 사용해야 한다.

BFS도 결국에는 모든 그래프를 커버할 수는 없기 때문에 예제 코드를 실행해보고 다양한 그래프 구조에서 BFS를 적용해 보는 연습이 필요할 것이다. 다음 글은 DFS와 BFS를 이용하는 문제에 대한 풀이가 되겠다.

- 같이 보면 좋은 글: DFS

[C++] 깊이 우선 탐색 (DFS)