너비 우선 탐색(BFS)

※이 포스팅은 나동빈님 강의를 듣고 정리한 것 입니다.※

https://www.youtube.com/watch?v=66ZKz-FktXo&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=16

---

너비 우선 탐색 (Breath-First-Search, BFS)입니다. 너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘입니다. 특히나 '맹목적인 탐색' 을 하고자 할때 사용하는 탐색 기법이고 미로찾기와 같은 곳에서 많이 활용이 됩니다. 이는 '최단 경로'를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용됩니다. 큐를 이용합니다.  

'BFS는 가까운 거를 먼저 탐색한다'라는 개념입니다.

 

큐와 그래프가 준비가 되었습니다. 

 

BFS는 맨 처음에 시작 노드(Start Node)를 큐에 삽입하면서 시작합니다. 또한 방문한 노드를 '방문 처리' 를 해줍니다. 

방문처리용 배열이 필요하겠죠?

시작 노드 1을 방문했습니다. 큐에 이 시작 노드 1을 삽입합니다. 

이제 BFS는 아래 알고리즘을 따라 작동합니다. 

1. 큐에서 하나의 노드를 꺼냅니다.

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입합니다. 

 

이 과정을 계속해서 반복하면 됩니다.

큐에 있던 1을 꺼내고 연결된 2와 3을 큐에 삽입했습니다. 

2를 꺼냅니다. 2와 연결된 노드 중 1,3 은 이미 방문을 끝냈음으로 4,5 를 큐에 삽입합니다. 아래 그림과 같아집니다. 

이제 큐에 있는 3을 꺼내보겠습니다. 3과 연결된 1과 2는 이미 방문 처리가 되어 있으므로 6,7를 방문하고 큐에 넣어줍니다.

그럼 모든 노드를 방문했습니다. 이제 큐에서 4,5,6,7 을 차례대로 꺼내주면 됩니다. 이미 모든 노드를 방문했기 때문에 차례로 다 꺼내집니다. 꺼낸 순서를 보면 1,2,3,4,5,6,7 입니다. 아무렇게나 탐색하는 것이 아니라 시작노드와 '가까운' 노드들부터 탐색이 이루어진다는 점에서 너비 우선 탐색이라고 합니다. 사실 저는 이름이 내용을 잘 담지 못한다고 생각을 하지만... 가까운 거리 우선 탐색! 이 더 맞는거 같아서ㅎㅎ 가까운 노드 부터 탐색을 하니깐 시작노드 1에서 가장 먼 4,5,6,7 이 나중에 탐색된 것을 알 수 있죠. 이제 C++ 코드를 구현하는 방법은 다음과 같습니다. C++ STL 라이브러리를 사용해줍니다. 

 

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

using namespace std;

int number = 7;
int c[8]; //방문처리 1~7까지 방문을 해주기 때문에 
vector<int> a[8]; //연결된 노드들 표시  

void bfs(int start){//시작 노드를 넣어준다 
	queue<int> q;
	q.push(start);
	c[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];//x와 인접한 노드  
			if(!c[y]){//방문했던 노드가 아니라면 
				q.push(y);
				c[y] = true;//방문함 
			}
		}
	}
}

int main(void){
	//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);
	
	//4과 5를 연결 
	a[4].push_back(5);
	a[5].push_back(4);
	
	//3과 6을 연결 
	a[3].push_back(6);
	a[6].push_back(3);		
	
	//3과 7을 연결 
	a[3].push_back(7);
	a[7].push_back(3);
	
	//6과 7을 연결 
	a[6].push_back(7);
	a[7].push_back(6);
	
	bfs(1);
	
	return 0;
} 

BFS 는 너비(거리)를 우선으로 탐색한다는 특성이 중요한 거고 이를 이용해 다른 알고리즘에 적용한다는 것이 핵심입니다. 그래서 BFS 자체로는 큰 의미가 없다고 생각해도 됩니다.

 

깊이 우선 탐색 포스팅입니다. 

https://com24everyday.tistory.com/110

깊이 우선 탐색(DFS)