[ 백준 ] 20924번 - 트리의 기둥과 가지 (C++)

https://www.acmicpc.net/problem/20924

20924번: 트리의 기둥과 가지

 

 

[ 문제풀이 ]

 

1. 그래프를 입력받고, list 배열에 저장합니다.

 

2. dfs를 이용하여 루트부터 탐색하면서 현재 노드까지의 길이를 저장하고, 그중 가장 긴 길이를 all에 저장합니다.

 

3. 자식 노드가 2개 이상인 노드의 길이 중 가장 짧은 길이를 gidung에 저장합니다.

 

4. gidung 과 all - gidung을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<vector>
 
using namespace std;
 
int N, R;
int a, b, d;
vector<pair<int, int>> list[200001];
int visited[200001];
int all;
int gidung = 987654321;
 
void dfs(int node, int dist)
{
    int cnt = 0;
    all = max(all, dist);
    for (auto& next : list[node]) {
        if (visited[next.first] == 0) {
            cnt++;
            visited[next.first] = 1;
            dfs(next.first, dist + next.second);
            visited[next.first] = 0;
        }
    }
 
    if (cnt >= 2) {
        gidung = min(gidung, dist);
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> R;
 
    for (int i = 0; i < N - 1; i++) {
        int a, b, d;
        cin >> a >> b >> d;
 
        list[a].push_back({ b,d });
        list[b].push_back({ a,d });
    }
 
    visited[R] = 1;
    dfs(R, 0);
 
    if (gidung == 987654321) {
        gidung = all;
    }
 
    cout << gidung << ' ' << all - gidung;
}