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

문제

접근 방법

DFS를 하면 되는데 입력받은 뒤 그래프마다 정렬을 한번 해줘야 한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> graph;
vector<int> visted;
int cnt = 0;
void dfs(int cur)
{
    for (int i : graph[cur])
    {
        if (visted[i])
            continue;
        visted[i] = ++cnt;
        dfs(i);
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M, R, n1, n2;
    cin >> N >> M >> R;
    graph = vector<vector<int>>(N + 1, vector<int>());
    visted = vector<int>(N + 1);
    for (int i = 0; i < M; ++i)
    {
        cin >> n1 >> n2;
        graph[n1].push_back(n2);
        graph[n2].push_back(n1);
    }
    for (int i = 1; i <= N; ++i)
    {
        sort(graph[i].begin(), graph[i].end(), greater<int>());
    }
    visted[R] = ++cnt;
    dfs(R);
    for (int i = 1; i <= N; ++i)
        cout << visted[i] << "\n";
    return 0;
}

풀이

예제를 보고 헷갈릴 수도 있는데 방문한 노드의 번호가 아닌 방문 순서를 차례로 출력하는 것임을 명심하면 된다.