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

20924번 : 트리의 기둥과 가지

---

문제)

시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다.

마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다. 

마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다.

기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 2개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 4번 노드다.

 

단, 위 그림과 같이 리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 된다.

또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다.

 

• 트리의 기둥은 루트 노드에서부터 기가 노드까지다. 위 그림에서 기둥은 1−2−3−4$1-2-3-4$ 이다.
  기둥의 길이는 기둥의 간선 길이의 합인 1 + 2 + 3 = 6 이 된다.
• 트리의 가지는 기가 노드에서부터 임의의 리프 노드까지다. 위 그림에서 가지는 4-5-6-7, 4-5-8, 4-9, 4-10-11, 4-10-2  총 5개가 있다.
  가지의 길이는 가지의 간선 길이의 합이다. 다행히도 가장 긴 가지의 길이 하나만 기재하면 된다. 4-10-12 가지가 간선 길이의 합 3 + 3 = 6 으로 가장 긴 가지이다.

마이크로는 시의 나무를 트리 자료 구조로 옮겼다. 그런데 과장이 마이크로에게 또 다른 업무를 지시했다! 너무 바쁜 마이크로를 대신해 트리의 기둥과 가장 긴 가지의 길이를 측정하자.

 

 

입력 :

첫 번째 줄에는 노드의 개수 N(1≤ N ≤200000)과 루트 노드의 번호 $(1≤ R ≤N)이 주어진다.

이후 N-1개의 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b)가 주어진다. 이는 a번 노드와 b번 노드가 연결되어있으며 이 간선의 길이가 d(1 ≤ d ≤1000)임을 의미한다. 노드는 1번부터 N번까지 정수 번호가 매겨져 있으며 같은 간선은 여러 번 주어지지 않는다. 

트리가 아닌 그래프는 입력으로 주어지지 않는다.

 

 

 

출력 :

나무의 기둥의 길이와 가장 긴 가지의 길이를 출력한다.

 

 

 

 

풀이)

 

// 20924. 트리의 기둥과 가지
#include <iostream>
#include <vector>
#include <tuple>
 
using namespace std;
 
int n, r;
vector<int> tree;
vector<vector<pair<int, int>>> vec;
 
int giga_node = 0;
int giga_prev = 0;
int max_leaf = 0;
 
void dfs(int cur, int prev)
{
    for (int i = 0; i < vec[cur].size(); i++)
    {
        if (vec[cur][i].first == prev) continue;
        // 가지가 몇개인지 계속 세어준다.
        // 가지가 1개라면 기둥이 이어지는 것이고,
        // 1 이상이라면 여러개의 가지가 뻗어나간 것이다.
        tree[cur]++;
        dfs(vec[cur][i].first, cur);
    }
}
 
int find_giga(int cur, int prev, int total)
{
    // 가지가 뻗어나간 곳이라면
    if (tree[cur] > 1)
    {
        // 해당 노드는 기가노드이고
        // 리프 노드로부터의 연산을 위해 이전 노드를 저장해놓는다.
        giga_node = cur;
        giga_prev = prev;
        return total;
    };
 
    for (int i = 0; i < vec[cur].size(); i++)
    {
        if (vec[cur][i].first == prev) continue;
        return find_giga(vec[cur][i].first, cur, total + vec[cur][i].second);
    }
 
    // 가지가 없더라도 기둥은 존재하므로
    // 여태 모은 total를 리턴해주어야 한다.
    return total;
}
 
void find_leaf(int cur, int prev, int total)
{
    // 기가노드부터 리프노드의 끝까지의 거리 중 
    // 가장 큰 값을 계속 저장한다.
    max_leaf = max(max_leaf, total);
 
    for (int i = 0; i < vec[cur].size(); i++)
    {
        if (vec[cur][i].first == prev) continue;
        find_leaf(vec[cur][i].first, cur, total + vec[cur][i].second);
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> r;
    tree.resize(n + 1, 0);
    vec.resize(n + 1, vector<pair<int, int>>());
 
    int a, b, c;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> c;
        // 방향이 없는 양방향 간선이다.
        vec[a].push_back({b, c});
        vec[b].push_back({a, c});
    }
 
    // 전체 트리를 파악하기 위함
    dfs(r, 0);
 
    // 기가노드 찾기
    cout << find_giga(r, 0, 0) << " ";
    // 기가노드로부터 리프노드의 끝까지 중 최댓값 찾기
    find_leaf(giga_node, giga_prev, 0);
    cout << max_leaf;
 
    return 0;
}
 

---

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

20924번: 트리의 기둥과 가지