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

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

 

그래프 입력을 받고 각 정점벡터를 내림차순으로 정렬한 다음에 의사코드에 나와있는 코드와 같이 구현해준다.

이때 전역변수를 사용하여 방문순서를 기록해주도록 하자.

 

 

정답코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void DFS(int node);
vector<vector<int>> graph;
vector<int> visited;
int order = 1;
int main()
{
	int n, m, r;
	cin >> n >> m >> r;

	graph.resize(n + 1);
	visited.resize(n + 1);
	fill(visited.begin(), visited.end(), 0);

	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].rbegin(), graph[i].rend());
	}

	DFS(r);

	for (int i = 1; i <= n; i++)
	{
		cout << visited[i] << "\n";
	}
}

void DFS(int node)
{
	visited[node] = order++;
	for (int next : graph[node]) {
		if (!visited[next]) {
			DFS(next);
		}
	}
}