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

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

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

DFS를 이용한 문제입니다.

노드의 방문 순서 및 노드 깊이를 구하는 문제였습니다.

 

방문 순서는 변수 하나를 통해 저장해주면 됩니다.

저는 Count 변수를 하나 만들어, 노드를 방문할 때마다 1씩 증가해 넣어줬습니다.

 

노드 깊이는 방문 순서와 다르게 다른 노드를 방문했다고 1씩 증가하는게 아닙니다.

이전 노드의 깊이에서 1을 더해야 함으로, dfs() 함수에 매개 변수를 만들어 저장해줬습니다.

 

마지막으로 두개를 곱해서 더할 때, int의 범위를 넘을 수 있음으로 long long int 형식으로 바꿔주는 것을 잊으시면 안됩니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
#define LL long long int

using namespace std;

int N, M, R;
vector<int> connect[100001];
LL check[100001];
LL depth[100001];
int Count = 1;

void dfs(int x, int cnt){
    depth[x] = cnt;
    check[x] = Count++;
    for(int i = 0 ; i < connect[x].size(); i++){
        int xx = connect[x][i];
        if(check[xx] != 0) continue;
        dfs(xx, cnt + 1);
    }
}

void solve(){
    LL sum = 0;
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end());
    }
    memset(depth, -1, sizeof(depth));
    dfs(R, 0);
    for(int i = 1; i <= N; i++){
        sum += check[i] * depth[i]; 
    }
    cout << sum;
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> R;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글 남겨주세요!