BFS (Breadth-First Search, 너비 우선 탐색)

[서론]

BFS는 DFS와 더불어 그래프 탐색의 기본적인 알고리즘이다.

DFS로 풀 수 있는 문제의 대부분은 BFS로 풀 수 있다. 갈 수 있는 모든 노드를 탐색하는 것은 결과적으로 같기 때문이다.

기본적인 정의와 동작 원리를 이해하고, 이차원 배열에서의 응용 문제들을 풀어보자.

 

BFS (Breadth-First Search, 너비 우선 탐색)

■ 개념

 그래프를 탐색할 때, 다음 level의 모든 노드를 먼저 방문하여 탐색하는 기법이다.

 즉, 인접한 모든 노드를 우선으로 방문하여 탐색하는 방법이라 할 수 있다.

■ 동작 원리

1번 노드에서 출발하는 다음과 같은 그래프에서 BFS가 어떻게 작동하는지 살펴보자.

- 1번 노드의 인접 노드인 2, 5, 7번 노드를 순서대로 방문한다.

- 2번 노드의 자식 노드를 모두 방문한다. 위의 경우에는 3번을 방문한다.

- 5번 노드의 자식 노드를 모두 방문한다. 위의 경우에는 자식 노드가 없으므로, 방문하지 않는다.

- 7번 노드의 자식 노드를 모두 방문한다. 위의 경우에는 8번을 방문한다.

- 3번 노드의 자식 노드를 모두 방문한다. 위의 경우에는 4, 6번을 순서대로 방문한다.

 

이 과정은 코드에서 큐(Queue)를 통해 구현된다. 큐를 사용해 위의 과정들을 다시 살펴보자.

초기 상태이다. 최초 방문하는 1을 큐에 삽입한다.

1을 방문했으므로, 큐에서 1을 꺼내고 1의 인접 노드인 2, 5, 7을 순서대로 큐에 삽입한다.

큐에서 2를 꺼낸다. 2의 인접 노드인 3을 큐에 삽입한다.

큐에서 5을 꺼낸다. 인접 노드가 없으므로, 아무 일도 일어나지 않는다.

다음으로 큐에서 7을 꺼낸다. 7의 인접 노드인 8을 큐에 삽입한다.

큐에서 3을 꺼낸다. 3의 인접 노드인 4, 6을 큐에 삽입한다.

이후 큐에 남은 노드들을 차례로 꺼낸다. 남은 노드들은 인접 노드가 없으므로 아무 일도 일어나지 않는다.

모든 원소를 꺼내고 큐가 빈 상태가 되면, 탐색을 마친다.

■ 구현

위의 예제 그래프를 BFS 방법으로 탐색하는 코드는 다음과 같다.

[코드]

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
vector<int> adj[9];
bool visit[9];
 
void bfs() {
    //노드들의 level을 확인하기 위해 pair 사용
    queue<pair<int, int>> que;
    que.push({ 1, 1 });
 
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        printf(" %d (level : %d)\n", cur.first, cur.second);
 
        for (int i = 0; i < adj[cur.first].size(); i++) {
            //모든 인접 노드들에 대해 방문 가능한지 확인
            int nextnode = adj[cur.first][i];
            if (!visit[nextnode]) {
                //반드시 큐에 넣기 직전에 visit 을 갱신해야 함.
                visit[nextnode] = true;
                que.push({ nextnode, cur.second + 1});
            }
        }
    }
}
 
void init() {
    adj[1].push_back(2);
    adj[1].push_back(5);
    adj[1].push_back(7);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(6);
    adj[7].push_back(8);
}
 
int main() {
    init();
    printf(" [방문 순서]\n");
    bfs();
 
    return 0;
}

 

[출력]

출력에서 방문한 노드들이 Level 순으로 정렬되어 나오는 것을 확인할 수 있다.

 

■ 이차원 배열에서의 BFS

DFS와 마찬가지로 이차원 배열에서의 응용 문제가 많이 나오는 편이다.

DFS와 마찬가지로 위와 같은 판에서 BFS로 모든 칸을 탐색하는 순서는 다음과 같다.

칸에 칠해진 색은 Level에 따라 구분했다.

여기서 알 수 있는 점은 출발점에 대해 Level이 n인 다른 한 칸은

출발점에서 n 칸 이동하여 갈 수 있는 칸이라는 것이다.

즉, 가중치가 없는 그래프에서 서로 다른 두 칸의 최단거리를 구할 수 있다.

 

예를 들어, 1에서 출발해 9로 가는 경로는 1->3->9, 1->4->10->18->9 ... 등 여러 가지 경우가 있지만,

최단 경로는 2칸 이동한 1->3->9 임을 BFS를 통해 알 수 있다.

왜냐 하면, 18번 칸에서 인접한 9번 노드는 18번 노드에 의해 방문되기 전에

큐에 의해 반드시 3번 칸의 인접 노드로써 먼저 방문되기 때문이다.

 

[응용 문제]

BOJ4179_불! :  www.acmicpc.net/problem/4179

문제의 요소들 중 BFS로 표현할 수 있는 것들에 대해 생각해보자.

4179번: 불!

BOJ1726_로봇 : www.acmicpc.net/problem/1726

이 문제는 단순히 칸에 대한 BFS로는 먼 길을 가야 한다. BFS에 다른 요소를 추가할 수 없을지 생각해보자.

1726번: 로봇