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

 

문제 24480번

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

 

이번에는 어제 풀었던 문제랑 다른 점이 하나 있다. 바로 인접 정점은 내림차순으로 방문한다는 것이다.

그렇기때문에 sort로 정렬하는 과정에서 greater<int>()만 뒤에 추가해주면 오름차순이 아닌 내림차순으로 정렬시켜줄 수 있다. 어제는 공부하고 풀었기 때문에 다음에는 안 보고 잘 풀 수 있을까 했는데 다행히 오늘 풀어봤을 때 잘 기억하고 있는 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> graph[100001];
bool visited[100001];
int result[100001];
int cnt = 0;

void dfs(int r) {
	if (visited[r] == true) {
		return;
	}
	visited[r] = true;
	cnt++;
	result[r] = cnt;
	for (int i = 0; i < graph[r].size(); i++) {
		dfs(graph[r][i]);
	}
}

int main() {
	int n, m, r;
	cin >> n >> m >> r;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {	//내림차순
		sort(graph[i].begin(), graph[i].end(), greater<int>());
	}
	dfs(r);
	
	for (int i = 1; i <= n; i++) {
		cout << result[i] << '\n';
	}

	return 0;
}