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

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

사용 언어: C++

 

풀이

24479번과 동일한 풀이이지만 sort만 내림차순으로 한다.

sort 함수에 greater<>을 넣어줘서 앞에 수가 뒤에 수보다 크면 true 리턴해서 내림차순으로 sort 된다.

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

vector<int> graph[100001];
bool visited[100001];
int order[100001];
int cnt = 1;

void dfs(int node)
{
    visited[node] = true;
    order[node] = cnt++;

    sort(graph[node].begin(), graph[node].end(), greater<>());

    for (int neighbor : graph[node])
    {
        if (!visited[neighbor])
        {
            dfs(neighbor);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    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);
    }

    dfs(R);

    for (int i = 1; i <= N; i++)
    {
        if (visited[i])
        {
            cout << order[i] << "\n";
        } else
        {
            cout << 0 << "\n";
        }
    }

    return 0;
}

24479번과 동일한 풀이이지만 sort만 내림차순으로 한다.

sort 함수에 greater<>을 넣어줘서 앞에 수가 뒤에 수보다 크면 true 리턴해서 내림차순으로 sort 된다.