<알고리즘/c++>너비 우선 탐색 / Breadth First Search (BFS)

너비 우선 탐색 이란?

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. -출처 위키 

 

 

 

그림을 보시면 너비를 먼저 탐색하면서 천천히 내려가는 방식의 탐색 기법입니다.

먼저 큐의 대한 개념이 들어가므로 큐에 대한 이전링크를 걸어두도록 하겠습니다.

큐 이전링크:

2019/10/14 - [C++(Math&알고리즘)] - <알고리즘/c++>큐(queue)

<알고리즘/c++>큐(queue)

 

저희가 사용할 그래프의 모습을 확인 해보겠습니다.

이러한 형태를 2차원 배열로 나타내보겠습니다.

int G[9][9] = { 
{0,1,1,0,0,0,0,0,0},  //0
{0,0,0,1,0,1,0,0,0},   //1
{0,0,0,0,0,0,1,0,1},   //2
{0,1,0,0,1,0,0,0,0},   //3
{0,0,0,1,0,1,0,0,0},   //4
{0,1,0,0,1,0,0,0,0},   //5
{0,0,1,0,0,0,0,1,1},   //6
{0,0,0,0,0,0,1,0,0},   //7
{0,0,1,0,0,0,1,0,0}    //8

};

위의 모습처럼 될것입니다.

그렇다면 어떻게 탐색하는지에 대해서 설명을 드리겠습니다.

 

 

설명을 드리자면 일단 0 노드 부터 시작을 할겁니다. 

그렇다면 0노드의 모두 인접 노드를 1의 값으로 표시하여 인접한 노드를 탐색을 합니다. 

그리고 모든 인접 노드들을 push를 해줍니다 0의 노드의 경우에는 1,2 노드가 인접해 있으므로 모두 저장을 해줍니다.

그리고 나머지를 모두 탐색하면 큐의 방식대로 pop을 해줍니다. 그러면 0의 노드가 나옵니다 즉  첫번째 노드의 탐색의 완료입니다 그다음엔 다시한번 검색할때 큐에 1,2는 탐색 예정이므로 1,2 인접노드들을 가지는 모든 노드들은 0으로 만들어줍니다. 그리고 큐의 첫번째 값을 가지고와서 다음 노드로 보냅니다 즉 i=queue[0] 됩니다. 

이후 같은 방법으로 하면될것 같습니다.

그렇다면 코드로 한번 확인해보겠습니다.

#include<iostream>
#include<Windows.h>
#include<vector>
using namespace std;
int G[9][9] = { 
{0,1,1,0,0,0,0,0,0},  //0
{0,0,0,1,0,1,0,0,0},   //1
{0,0,0,0,0,0,1,0,1},   //2
 {0,1,0,0,1,0,0,0,0},   //3
{0,0,0,1,0,1,0,0,0},   //4
{0,1,0,0,1,0,0,0,0},   //5
{0,0,1,0,0,0,0,1,1},   //6
{0,0,0,0,0,0,1,0,0},   //7
{0,0,1,0,0,0,1,0,0}    //8

};
vector<int>QueueData;

먼저 그래프의 이차원 배열의 모습과 QueueData를 저장해줄 전역변수로 선언을 해줍니다.

메인을 확인 해보겠습니다.

int main() {


	BFS(0, 0);

	system("pause");
	return 0;
}

BFS 함수를 지정해주고 0노드 부터 시작할거여서 i,j 모두 0으로 받아줍니다.

BFS 함수입니다.

int BFS(int i,int j) {

	if (QueueData.size() < 1) {
		QueueData.push_back(j);
	}

	if (G[i][j] == 1) {
		for (int k = 0; k < 9; k++) {
			G[k][j] = 0;
		}

		QueueData.push_back(j);
	}


	if (j < 8 ) {
		j = j + 1;
		return BFS(i,j);
	}
	else {
		i=QueueData[0];
		cout << i;
		QueueData.erase(QueueData.begin());
		j = 0;
		if (QueueData.size() < 1) {

			return -1;
		}
		return BFS(i, j);

	}

	


}

DFS 와 마찬가지로 재귀함수를 이용할겁니다. 

모르시면 이전링크 피보나치 수열 코드를 한번 확인해주세요 

피보나치 수열 이전링크 : 

2019/10/14 - [C++(Math&알고리즘)] - <알고리즘/C++> 동적 계획법/피보나치 수열(Dynamic Programming)

<알고리즘/C++> 동적 계획법/피보나치 수열(Dynamic Programming)

먼저 큐에 맨 처음  탐색할 노드를 넣어줍니다.

if (QueueData.size() < 1) {
		QueueData.push_back(j);
	}

인접노드를 queue에 push 해줍니다. 그런데 인접노드를 전부 넣어줬으니 다른 노드들은 더이상 그 노드를 갈필요가 없으면 전부 다른 노드들을 0으로 바꿔줍니다. 

if (G[i][j] == 1) {
		for (int k = 0; k < 9; k++) {
			G[k][j] = 0;
		}

		QueueData.push_back(j);
	}

현재 노드의 인접노드가 존재여부를 끝까지 해줘야합니다.

if (j < 8 ) {
		j = j + 1;
		return BFS(i,j);
	}

j=8이되어 현재 노드 탐색을 완료를 알려줍니다. 그리고 큐 데이터에서 pop을 해줍니다. 

만약 더이상 큐데이터의 탐색해야할 노드들이 존재하지 않다면 BFS를 종료합니다. 

else {
		i=QueueData[0];
		cout << i;
		QueueData.erase(QueueData.begin());
		j = 0;
		if (QueueData.size() < 1) {

			return -1;
		}
		return BFS(i, j);

	}