[C++][백준 24483] 알고리즘 수업 - 깊이 우선 탐색 5

문제

접근 방법

DFS를 하면서 깊이, 방문 순서를 신경 써야 하는 문제입니다.
깊이의 경우에는 함수의 매개변수를 활용하여 기록해 주면 되고 방문 순서는 전역 변수로 활용해 주면 됩니다. (또는 참조 매개변수를 활용하는 방법도 있습니다)

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

int N, M, R, t;
ll answer;
vector<vector<int>> graph;
vector<bool> isVisited;

void input()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M >> R;

    isVisited = vector<bool>(N + 1);
    graph = vector<vector<int>>(N + 1, vector<int>());

    while (M--)
    {
        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());
    }
}

void dfs(int curNode, ll depth)
{
    isVisited[curNode] = true;

    answer += depth * ++t;

    for (int nextNode : graph[curNode])
    {
        if (isVisited[nextNode])
        {
            continue;
        }

        dfs(nextNode, depth + 1);
    }
}

int main()
{
    input();
    dfs(R, 0);
    cout << answer;
    return 0;
}

풀이

등수가 괜찮게 나와서 기록해 보았습니다.

조심해야 할 점은 di x ti의 값이 int의 범위를 벗어날 수 있다는 점입니다.
한 줄로 쭉 이어진 형식의 그래프라고 할 때 N^2 정도의 값이 나오는데 N^2은 100억이기에 int의 범위를 벗어납니다.

오름차순으로 방문해야 하기에 미리 모든 정점에 대해서 오름차순으로 방문할 수 있게 정렬을 해주는 것이 좋습니다.