[백준/BOJ] 24480번 알고리즘 수업 - 깊이 우선 탐색 2 (C/C++)

백준 온라인 저지(BOJ) 24480번 알고리즘 수업 - 깊이 우선 탐색 2

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

* 사용언어 : C언어, C++

 

1. 문제

graph 를 DFS(깊이 우선 탐색)으로 탐색할 때

1번 정점부터 N번 정점까지 방문한 순서를 출력

(인접 정점은 내림차순으로 방문)

 

2. 풀이

앞서 풀어본 24479번 문제와 거의 유사한 코드로 구현하였습니다.

https://rightbellboy.tistory.com/242

[백준/BOJ] 24479번 알고리즘 수업 - 깊이 우선 탐색 1 (C/C++)

 

다른 점은 vector 를 sort 할 때 내림차순으로 처리하기 위해

begin, end 대신 rbegin, rend 함수를 사용했다는 점 입니다.

 

그 외에는 동일하니 추가 설명 없이 마치겠습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24480_알고리즘 수업 - 깊이 우선 탐색 2
10004KB	112ms
*/
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int LM = 100001;
vector<int> graph[LM];
int visited[LM], seq = 1;

void dfs(int r) {
	visited[r] = seq++;

	for (int i = 0; i < graph[r].size(); i++) {
		if (!visited[graph[r][i]]) dfs(graph[r][i]);
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, s, u, v;
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		if (u != s) graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) sort(graph[i].rbegin(), graph[i].rend());
	dfs(s);

	for (int i = 1; i <= n; i++) printf("%d\n", visited[i]);
	return 0;
}