BFS(Breadth First Search)

BFS는 너비 우선 탐색이다.

이걸 위해서 직접 만들었다. 역시 대단해 ㅎㅎㅎㅎㅎㅎ

본론으로 BFS는 너비 탐색으로 말 그대로 넓게 퍼져가면서 탐색한다 생각하면 된다.

과정은 간단하다.

큐(Queue)에 하나하나 넣어서 대기 시키는 느낌이랄까...

코드는 다음과 같다.

void bfs(int num) {
	queue<int> q;
	q.push(num);
	check[num] = true;
	int x, y;
	while(!q.empty()) {
		x = q.front();
		q.pop();
		cout << x << " ";
		for(int i = 0; i < arr[x].size(); i++) {
			y = arr[x][i];
			if(!check[y]) {
				check[y] = true;
				q.push(y);
			}
		}	
	}
}

위의 그림 에서는 num = 1 부터 시작할 것이다.

check배열은 확인을 했는지 안 했는지를 확인 해주기 위함이다.

가지 않았으면 check는 false가 되고, 큐에 해당 노드를 넣어 대기시켜준다는 느낌?!?!

 

while문으로 계속 돌리면서 queue에 있는 값을 빼고 확인하고 반복한다.

 

많이 쓰이는 알고리즘 같은데 막상 써보려 하면 머리가 터질듯 ㅠ

 

+ 최단거리 쓸때 쓰면 좋다!!!!!!!