[C++] BFS(너비 우선 탐색)구현하기

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

 

 위의 문장은 너비 우선 탐색에 대한 정의이다. 여기서 잘 봐야 할 단어는 "인접한"이다. 처음 BFS(너비 우선 탐색)을 공부할 때 단어 그대로 너비 우선 탐색으로 이해했기 때문에 헷갈리는 부분이 있었다. 

 우리는 대부분 아래와 같이 깊이감이 있는 그래프를 그린다. 너비 우선 탐색이라고 하여 나는 a -> b -> d -> ... 순으로 탐색을 해야한다고 생각했으나.. 위에서 말했듯 "인접한" 정점을 우선적으로 탐색하는 것이므로 a -> b -> c -> d ... 순으로 탐색한다.

위키피디아 출처

여기까지 하면 깊이 우선 탐색인 DFS와 다른 점이 무엇이냐? 라고 할 수도 있다. DFS는 e를 탐색한 후 h를 탐색하겠지만 BFS에서는 a와 인접한 b와 c를 탐색한 후 b와 인접한 정점인 d와 e를 탐색했으니 그 이후엔 c를 탐색한다. 즉, 인접한 정점을 우선적으로 탐색하지만 depth를 파고들어 탐색하는 것이 아닌 같은 level에 있는 정점들의 인접한 정점을 또 탐색하는 방법이다.

 

이러한 BFS를 구현하려면 queue 자료구조를 이용해야 한다.

---

BFS 구현을 그림으로 나타낸다면 다음과 같다.

제일 처음 a라는 정점을 탐색하므로 queue에는 a 정점이 들어가있다. 이제 여기서 a와 인접한 b와 c를 탐색하게 된다.  

 

앞서 있던 a의 인접한 정점을 탐색하고 a는 queue에서 pop되며, 방문했던 정점을 나타내는 visit 배열에 들어가게 된다. 그리고 a의 인접한 정점인 b와 c가 queue에 push된다. 이후 queue의 특성에 따라 b의 인접한 정점을 탐색하고 b도 pop하게 된다.

b와 인접한 정점인 d와 e가 queue에 push된다. 하지만 c의 순서가 먼저이기 때문에 다음 탐색 순서는 c가 된다.

여기서 DFS와의 차이점을 볼 수 있다. DFS라면 c보다 d를 먼저 탐색하게 될 것이다. 하지만 BFS 방식에서는 인접한 정점 탐색 후 바로 같은 level의 정점을 탐색한다.

 

c의 인접한 정점인 f와 g도 queue에 알맞게 push되었다. 이후 같은 방법으로 탐색을 하며 queue에 아무런 data도 없다면 탐색을 멈춘다. 

 

 그렇다면 visit의 역할은 무엇일까?  b에서 인접한 정점을 탐색할 때 우리는 자연스럽게 depth를 높여가며 d와 e만 탐색했지만 사실 a도 b의 인접한 정점이다. 하지만 a는 이미 탐색한 정점이기에 다음 탐색에서 제외를 시켜줘야한다. 이를 위해 탐색한 정점을 visit 배열에 넣어주고, 이후 탐색에서 제거될 수 있도록 조건을 걸어준다.

---

<코드 구현> _ 참고 : https://hongku.tistory.com/156 [IT에 취.하.개.:티스토리]

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

int number = 8;
int visit[8];
vector<int> a[9];

void bfs(int start){
    queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()){ // 큐에 값이 없을 때까지 반복
        int x = q.front();
        q.pop();
        printf("%d ", x);
        for(int i=0; i< a[x].size(); i++){
            int y = a[x][i];
            if(!visit[y]){ //이전에 탐색했던 정점이 아니라면
                q.push(y);
                visit[y] = true; 
            }
        }
    }
}

int main(void){
    
    // a과 b를 연결 
    a[1].push_back(2);
    a[2].push_back(1);
    
    // a과 c을 연결 
    a[1].push_back(3);
    a[3].push_back(1);
    
    // b와 d를 연결 
    a[2].push_back(4);
    a[4].push_back(2);

    // b와 e를 연결 
    a[2].push_back(5);
    a[5].push_back(2);
    
    // e와 h를 연결 
    a[5].push_back(8);
    a[8].push_back(5);
    
    // c과 f을 연결 
    a[3].push_back(6);
    a[6].push_back(3);
    
    // c과 g을 연결 
    a[3].push_back(7);
    a[7].push_back(3);
    
    // a번 노드부터 bfs 탐색 실행 
    bfs(1);
    
    return 0;
}

---

실제 BFS를 이용하는 문제에서는 위의 코드와는 조금 다른 방식으로 접근된다. 이후 글에서 프로그래머스의 '카카오프렌즈 컬러링북' 문제를 통해 BFS가 문제 해결 방식에서 어떻게 구현되는 지 좀 더 자세히 보고자 한다.