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

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

24445번: 알고리즘 수업 - 너비 우선 탐색 2

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <map>
#include <set>
#include <queue>
using namespace std;
struct Cmp {
	bool operator()(const int& v1, const int& v2) const {
		return v1 > v2;
	}
};
int N, M, R, cnt, ans[100001];
bool visit[100001];
map<int, set<int, Cmp>, Cmp> arr;
void bfs(register int r) {
	ans[r] = ++cnt;
	visit[r] = true;
	queue<int> q;
	q.push(r);
	while (!q.empty()) {
		auto u = q.front(); q.pop();
		for (auto iter = arr[u].begin(); iter != arr[u].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;
	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);
	cnt = 0;
	bfs(R);
	for (register int i = 1; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

이전 '알고리즘 수업 - 너비 우선 탐색 1'과 동일한 문제이지만 탐색할 대상이 내림차순으로 된 상태로 시작한다는 차이만 존재합니다.

아래 문제를 선행하시길 권장합니다.