너비 우선 탐색(BFS)

너비 우선 탐색(Breadth First Search):

특정 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 알고리즘.

 

최단 경로를 찾아준다는 점에서 최단 길이를 보장해야 할 때 많이 사용함. (ex. 미로찾기)

선입선출의 특성을 가진 큐를 이용하는데 큐는 너비 우선 탐색을 가능하도록 해준다.

 

1. 시작 노드를 큐에 삽입하면서 방문처리.
2. 큐에서 하나의 노드를 꺼낸다.
3. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입.
4. 2, 3번 과정을 반복하면 시작 노드에서 거리가 가까운 순서대로 출력이 될 것임.

 

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int n = 7;
int checked[7];
vector<int> arr[8];

void bfs(int start) {
	queue<int> q;
	q.push(start);
	checked[start] = true;

	while(!q.empty()) {
		int x = q.front();
		q.pop();
		printf("%d ",x);
		for(int i = 0; i<arr[x].size(); i++) {
			int y = arr[x][i];
			if(!checked[y]) {
				checked[y] = true;
				q.push(y);
			}
		}

	}
}

int main() {
	// 연결된 노드들을 나타내고, 인접 노드도 표현됨. 
	arr[1].push_back(2);
	arr[2].push_back(1);
	
	arr[1].push_back(3);
	arr[3].push_back(1);
	
	arr[2].push_back(3);
	arr[3].push_back(2);
	
	arr[2].push_back(4);
	arr[4].push_back(2);
	
	arr[2].push_back(5);
	arr[5].push_back(2);
	
	arr[3].push_back(6);
	arr[6].push_back(3);
	
	arr[3].push_back(7);
	arr[7].push_back(3);
	
	arr[4].push_back(5);
	arr[5].push_back(4);
	
	arr[6].push_back(7);
	arr[7].push_back(6);
	
	bfs(1);
	 
	return 0;
}