[알고리즘] BFS(너비 우선 탐색)

1. Breadth First Search (BFS, 너비 우선 탐색

1. 완전 탐색 알고리즘
 - 모든 경우의 수를 탐색하는 알고리즘

2. 시작점에서 가까운 점부터 탐색하는 방식
 - 개미굴에 물을 부어서 물이 점점 안 쪽으로 스며들어가는 방식과 비슷하다.

출처 : 위키백과, https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

2. 장점

1) 출발노드에서 목표 노드까지의 최단 길이 경로를 보장한다.

 

3. 단점

1) 경로가 매우 길 경우에는 탐색 기지가 급격히 증가하여 많은 기억 공간을 필요로 한다.

 

4. 구현

• Queue를 통해 구현
• 아래 3가지 구조로 나눌 수 있다.

1) 시작점 셋팅
2) 현재 방문 노드를 Queue에서 pop하기
3) 다음으로 방문할 노드 Queue에 삽입

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

using namespace std;

bool visited[11];
vector<int> graph[11];

void bfs(int start_node)
{
	// 1. 시작점 세팅
	queue<int> q;
	q.push(start_node);
	visited[start_node] = true;	// 방문 여부 체크

	while (!q.empty())
	{
		// 2. 현재 방문 노드를 Queue에서 pop하기
		int current_node = q.front();
		q.pop();
		cout << current_node << " ";

		// 3. 다음으로 방문할 노드 Queue에 삽입
		for (int index = 0; index < graph[current_node].size(); index++) {
			int next_node = graph[current_node][index];

			if (visited[next_node]) continue;

			visited[next_node] = true;
			q.push(next_node);
		}
	}
}

int main() {
	// graph 생성
	graph[1].push_back(2);
	graph[1].push_back(3);

	graph[2].push_back(4);
	graph[2].push_back(5);

	graph[3].push_back(6);
	graph[3].push_back(7);

	graph[5].push_back(8);

	// BFS (넓이 우선 탐색) 알고리즘
	bfs(1);

	return 0;
}

 

5. BFS(너비 우선 탐색) 문제 모음집

https://www.acmicpc.net/problem/14940

14940번: 쉬운 최단거리

https://www.acmicpc.net/problem/21736

21736번: 헌내기는 친구가 필요해

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/14502

14502번: 연구소

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

https://www.acmicpc.net/problem/16946

16946번: 벽 부수고 이동하기 4