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

문제링크 : https://www.acmicpc.net/problem/24483

24483번: 알고리즘 수업 - 깊이 우선 탐색 5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 
const int MOD = 1000000;

int N, M, R, cnt=1;
vector<int>vec[100001];
ll visited[100001], seq[100001], sum=0; 

void dfs(int cur, int depth)
{
    visited[cur]=depth; //깊이 저장 및 방문체크
    seq[cur] = cnt++; //방문순서 저장
    for(int i=0; i<vec[cur].size(); i++)
    {
        int next = vec[cur][i];
        if(visited[next]!=-1) continue;
        dfs(next, depth+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> M >> R;
    while(M--)
    {
        int u, v;
        cin >> u >> v;
        vec[u].push_back(v); //무방향 그래프
        vec[v].push_back(u);
    }

    for(int i=1; i<=N; i++) sort(vec[i].begin(), vec[i].end()); //오름차순 정렬
    memset(visited, -1, sizeof(visited));
    dfs(R, 0);
    for(int i=1; i<=N; i++) sum += visited[i] * seq[i]; //깊이*방문순서
    cout << sum;

    return 0;
}

 

백준 24481번 문제에서 출력 요구사항이 변경된 문제이다.

기존에는 각 깊이를 출력하는 것이었지만 이번엔 모든 노드에 대한 깊이*방문순서를 더해준 합을 출력해야 한다.

 

노드에 대한 깊이는 기존 깊이를 저장했던 visited 배열을 사용하면 된다.

방문순서는 따로 seq 배열을 선언하여 사용하였다.

방문순서는 1부터 차례로 증가하므로 이를 위한 변수 cnt를 1로 초기화하여 선언하고, 매 재귀마다 방문순서가 1 증가하기에 seq[cur]에 cnt++로 방문후 순서가 증가되도록 해주었다.

 

이후 sum에 각 깊이와 방문순서를 곱한 것을 모든 노드에 대해 행해주고, 이를 더해 출력하면 된다.

이때 주의해야하는 것은 위 계산과정에서 int 범위를 초과할 가능성이 생기기에 관련된 값들을 long long으로 선언해주어야 한다.

 

참고링크 : https://blob-thinking.tistory.com/364

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