[C/C++] 실전 알고리즘 강좌 16강. 너비 우선 탐색(Breath First Search)

학습 내용

---

너비 우선 탐색(Breath First Search)

너비 우선 탐색(Breath First Search, BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘이다. 특히 '맹목적인 탐색' 목적으로 사용할 수 있는 기법이다. 너비 우선 탐색은 기본적으로 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용한다. 필요한 것은 큐(Queue)이며 선입선출의 특징을 가지고 있기 때문에 너비 우선 탐색을 가능하게 한다.

 

BFS는 맨 처음 시작 노드(Start Node)를 큐에 삽입하면서 시작한다. 또한 시작 노드를 방문했다는 표시로 '방문 처리'를 해주도록 한다. 아래의 예시에서는 진한 검은색으로 표시하였다.

 

이제 BFS는 다음과 같이 간단한 알고리즘에 따라서 작동한다.

1. 큐에서 하나의 노드를 꺼낸다.
2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

위의 1번과 2번을 계속해서 반복하면 된다. 아래는 BFS의 작동 순서를 보여주는 예시이다.

 

출처 : https://www.codesdope.com/course/algorithms-bfs/

출처 : https://www.codesdope.com/course/algorithms-bfs/

 

위의 예시에서 맨 처음 노드인 1과 가까운 노드부터 탐색이 이루어지는 것을 알 수 있다. 이를 C++ 소스코드로 구현하면 다음과 같다. 

 

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int c[8];	// c는 방문 처리를 위한 배열이다
vector<int> a[8];
    
void bfs(int start){
    queue<int> q;
    q.push(start);
    
    c[start] = true;
    while(!q.empty()){	// q의 맨 앞의 숫자를 가져와 복사, 삭제, 출력 후 연결된 숫자들을 q에 삽입
        int x = q.front();
        q.pop();
        cout << x << ' ';
        for(int i = 0; i < a[x].size(); i++){
            int y = a[x][i];
            if(!c[y]){
                q.push(y);
                c[y] = true;
            }
        }
    }
}

int main()
{
    // 1과 연결된 노드 작성
    a[1].push_back(2);
    a[2].push_back(1);
    
    a[1].push_back(5);
    a[5].push_back(1);
    
    a[1].push_back(3);
    a[3].push_back(1);
    
    // 2와 연결된 노드 작성
    a[2].push_back(6);
    a[6].push_back(2);
    
    a[2].push_back(4);
    a[4].push_back(2);
    
    // 5와 연결된 노드 작성
    a[5].push_back(4);
    a[4].push_back(5);
    
    // 3과 연결된 노드 작성
    a[3].push_back(4);
    a[4].push_back(3);
    
    a[3].push_back(7);
    a[7].push_back(3);
    
    bfs(1);		// 실행 결과 : 1 2 5 3 6 4 7
    
    return 0;
}

 

 

이러한 BFS는 너비를 우선으로 하여 탐색한다는 특징이 중요한 것이고, 이를 이용해 다른 알고리즘에 적용한다는 것이 핵심이다. BFS 자체로는 큰 의미가 없다고 보면 된다.

 

 

 

참고자료

Breadth First Search (BFS) in Graphs