[백준] 트리의 지름(1967번)

1967번: 트리의 지름 (acmicpc.net)

문제 요약

트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 구하시오. (단, 루트 노드는 1이다.)

 

아이디어

한 노드에서 자식 노드까지의 거리 가장 큰 2개를 더하여 그 최댓값을 구한다.

 

풀이과정

이러한 형태의 트리가 있을 때 트리의 깊이를 알 수 있다.

깊이가 가장 깊은 것 부터 연산하여 자신의 부모 노드에 간선의 가중치+max(D[그 노드의 번호]) 를 기억한다.

D[6]=D[7]+15, D[6]=D[8]+4, D[6]=D[9]+9 로

D[6]에는 {15, 9, 4, 0}이 기억되어 있다. (0은 초기값)

이러한 연산을 계속한다면

 

D의 값은 이러할 것이다.

그러면 K에 D안에 값들의 최대값 2개를 더하는 연산을 한다.(K초기값 : -1)

K=max(K, D[1][0]+D[1][1])  --> K=24   (D[1][0]=19, D[1][1]=5)

 

K=max(K, D[2][0]+D[2][1])  --> K=24   (D[2][0]=3, D[2][1]=1)

 

K=max(K, D[3][0]+D[3][1])  --> K=24   (D[2][0]=18, D[2][1]=0)

...

K=max(K, D[6][0]+D[6][1])  --> K=24   (D[2][0]=15, D[2][1]=9)

...

K=max(K, D[9][0]) --> K=24 (D[9][0]=0)

 

으로 트리의 지름은 K=24가 된다.

 

코드 (C++)

#include <bits/stdc++.h>
using namespace std;
int c2[10010], c3[10010];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n; cin>>n;
    vector<int> A[10010];
    for(int i=1; i<n; i++)
    {
        int a, b, c; cin>>a>>b>>c;
        A[a].push_back(b);
        c3[b]=a; c2[b]=c;
    }

    priority_queue<pair<int, int> > B;
    priority_queue<int> D[10010];
    queue<int> a; a.push(1);
    B.push({0, 1}); D[1].push(0);

    while(!a.empty())
    {
        int b=a.front(), P=B.top().first;
        a.pop(); D[b].push(0);
        for(int i=0; i<A[b].size(); i++)
        {
            a.push(A[b][i]);
            B.push({P+1, A[b][i]});
        }
    }

    while(!B.empty())
    {
        int b2, d;
        b2=B.top().second;
        d=D[b2].top()+c2[b2]; B.pop();

        D[c3[b2]].push(d);
    }

    int k=0;
    for(int i=1; i<=n; i++)
    {
        int p=0;
        for(int j=0; j<2 && !D[i].empty(); j++)
        {
            p+=D[i].top(); D[i].pop();
        }

        if(i==1) k=p;
        k=max(k, p);
    }

    cout<<k;

    return 0;
}