알고리즘 수업 - 너비 우선 탐색 1 (feat. 백준, 24444번)

알고리즘 수업 - 너비 우선 탐색 1
https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <queue>
using namespace std;
int N, M, R, cnt, ans[100001];
bool visit[100001];
map<int, set<int>> arr;
void bfs(int r) {
	ans[r] = ++cnt;
	visit[r] = true;
	queue<int> q;
	q.push(r);
	while (!q.empty()) {
		auto key = q.front(); q.pop();
		for (auto iter = arr[key].begin(); iter != arr[key].end(); ++iter)
			if (!visit[*iter])
				ans[*iter] = ++cnt, visit[*iter] = true, q.push(*iter);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M >> R;
	cnt = 0;
	memset(ans, 0, sizeof(ans[0]) * (N + 1));
	memset(visit, false, N + 1);
	for (register int m = 0, u, v; m < M; ++m)
		cin >> u >> v, arr[u].insert(v), arr[v].insert(u);
	bfs(R);
	for (register int i = 1; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*​

1. 깊이 우선 탐색 DFS와 너비 우선 탐색 BFS의 차이는 한 노드에 대해서 연관된 항목으로 탐색을 이어갈 것인지 아닌지 입니다.
2. 예로, 1-2 1-3 2-3 이라는 간선 조건이 있다고 한다면, DFS는 1-2 2-3 1-3 의 순서로 탐색을 진행합니다. 왜냐하면 1을 key로 2를 탐색했고, 탐색된 2가 다음 key가 되기 때문입니다.
3. 하지만 동일한 간선 조건이 있을때, BFS는 1-2 1-3 2-3 의 순서로 탐색을 진행합니다. 왜냐하면 1을 key로 탐색한다면 1이라는 key를 모두 탐색한 이후 다음 key를 탐색 조건으로 갖기 때문입니다.
4. 이러한 특성으로 동일한 문제임에도 DFS와 BFS는 다른 정답을 도출하기도 합니다.