[C/C++] 너비 우선 탐색(BFS)

너비 우선 탐색이란?

너비 우선 탐색(Breadth-first search, BFS)은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

 

너비 우선 탐색은 큐와 관련 있습니다.

 

예를 들어 다음과 같이 연결된 이진트리가 있습니다.

 

 

이진 트리

 

 

가장 먼저 루트 노드를 방문하고 방문했다는 체크를 해줍니다.

큐 1

방문체크 1

 

큐에서 하나의 노드를 꺼내고 인접한 노드를 검사하여 큐에 차례대로 넣습니다.

큐 2-3

방문체크 1-2-3

 

다시 큐에서 하나의 노드를 꺼내고 인접한 노드를 검사하여 큐에 넣습니다. 2를 꺼낼 차례입니다. 3은 큐에 있으므로 4와 5를 넣어줍니다.(이미 방문한 노드는 넣지 않습니다.)

큐 3-4-5

방문체크 1-2-3-4-5

 

반복해서 큐에서 하나의 노드를 꺼내고 인접한 노드를 검사하여 큐에 넣습니다. 3을 꺼낼 차례인데 방문하지 않은 인접한 노드가 없습니다.

큐 4-5

방문체크 1-2-3-4-5

 

이후 4와 5가 큐에서 나오게 됩니다. 5를 꺼낼 때 방문하지 않은 인접한 노드가 없으므로 탐색이 끝나게 됩니다.

BFS의 동작 핵심은 다음과 같습니다.

 

1. 루트 노드 방문 후 방문 체크

2. 큐에서 꺼낸다.

3. 꺼낸 노드와 연결된 노드를 방문하고 방문 체크

4. 2, 3번을 반복한다.

 

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

int check[6];	//방문체크
vector<int> a[5];

void bfs(){
	queue<int> q;
	q.push(1);	//1번 루트노드넣기
	check[1] = true;	//1번 루트노드방문체크
	while(!q.empty()){
		//queue에 있는 front노드를 꺼냅니다. 
		int front = q.front();
		q.pop();
		printf("%d ", front);
		//꺼낸 노드와 인접한 노드를 방문하고 queue에 넣습니다.
		for(int i=0;i<a[front].size();++i){
			int x = a[front][i];
			while(!check[x]){	//이미 방문했으면 넣지 않습니다.
				q.push(x);
				check[x] = true;	//방문하면 check 
			}
		}
	}
}

int main(){
	//1과 2연결 
	a[1].push_back(2);
	a[2].push_back(1);
	//1과 3연결 
	a[1].push_back(3);
	a[3].push_back(1);
	//2와 3연결 
	a[2].push_back(3);
	a[3].push_back(2);
	//2와 4연결 
	a[2].push_back(4);
	a[4].push_back(2);
	//2와 5연결 
	a[2].push_back(5);
	a[5].push_back(2);
	
	bfs();
	
	return 0;
}

 

결과값:

1 2 3 4 5

 

지금 까지 너비 우선 탐색의 동작 원리에 대해 알아봤습니다. BFS는 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장합니다. 하지만 경로의 길이가 길면 많은 메모리를 사용하게 됩니다.