알고리즘 수업 - 깊이 우선 탐색 1 (feat. 백준, 24479번)

알고리즘 수업 - 깊이 우선 탐색 1
https://www.acmicpc.net/problem/24479

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string.h>
#include <set>
#include <map>
using namespace std;
int N, M, R, cnt, ans[100001];
bool visit[100001];
map<int, set<int>> arr;
void dfs(int r) {
	ans[r] = ++cnt;
	visit[r] = true;
	for (auto iter = arr[r].begin(); iter != arr[r].end(); ++iter)
		if (!visit[*iter])
			dfs(*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 i = 0, u, v; i < M; ++i)
		cin >> u >> v, arr[u].insert(v), arr[v].insert(u);
	dfs(R);
	for (register int i = 1; i <= N; ++i)
		cout << ans[i] << "\n";
	return 0;
}
// *&)*@*

1. dfs의 기본 개념을 알 수 있는 좋은 문제입니다.
2. u-v는 양방향 간선이라고 문제에서 제시되어 있습니다.
3. 입력된 u-v 간선은 오름차순으로 정렬되어 있어야 합니다.
4. u-v로 가는 경우에 대해서 1번을, v-x로 가는 경우에 대해서 2번을 부여하는 형태로 깊이 우선 탐색이 진행됩니다. (u-v v-x x-y y-z 와 같이)