[백준] 1167 트리의 지름(C++)

문제

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

1167번: 트리의 지름

 

 

풀이

트리에서의 지름은 원과 마찬가지로 내부의 두 점 사이의 거리가 가장 먼 길이를 말합니다.
원에서 가장 먼 두 점은 원 둘레 위의 한 점에서 가장 먼 둘레위의 점입니다.
트리에서도 마찬가지로 적용할 수 있습니다. 리프노드에서 리프노드까지의 거리중 가장 먼 것을 구하면 됩니다.

 

한 노드에서 가장 먼 (리프)노드를 구하고, 그 노드에서 다시 가장 먼 (리프)노드까지의 거리를 구하면 그것이 지름이 됩니다.

 

당연히 이렇게만 설명하면 부족할 수 있기 때문에 예시를 들어 알아봅시다.

 

그림과 같은 그래프가 있을 때의 지름을 구해봅시다.

 

트리는 임의의 노드를 루트로 설정할 수 있으므로 1번 노드를 루트로 하여 가장 먼 리프 노드를 구하겠습니다.

1번노드로부터 9만큼 떨어진 7번 노드가 가장 멀리 떨어져있는 노드입니다.
이제 다시 7번 노드로부터 가장 멀리 떨어진 노드를 구해봅시다.

아까의 트리에서 7번노드를 루트로하여 다시 그린 모습입니다.
7번 노드와 가장 멀리 떨어져 있는 노드는 9번 노드로 16의 거리 만큼 떨어져 있습니다.

 

트리의 지름을 이루는 노드는 7-4-2-1-3-5-9 가 되고, 지름은 16이 됩니다.

한 점으로부터 가장 먼 노드를 구하는 과정을 두 번 반복하면 됩니다. 이때 DFS 탐색으로 멀리있는 노드를 구했습니다.

 

 

증명

그럼 이제 왜 임의의 노드 A에서 가장 먼 노드 B, B노드에서 가장 먼 노드 C 로 만든 BC의 거리가 지름이 되는지 증명해봅시다.
임의의 노드 A에서 가장 먼 노드 B가 항상 지름의 양 끝점 중 하나에 포함된다면 BC가 지름이 된다는 것은 자명한 사실입니다. 따라서 노드 B가 지름의 끝 점으로 항상 포함됨을 보이면 됩니다.

 

이는 임의의 A 노드 에서 가장 먼 노드 B가 존재하고, 트리의 지름의 양끝 점은 D, E 노드로 이루어져 있다고 가정했을 때의 모순을 보이면 됩니다.

 

아래의 3가지 경우의 모순을 찾아 증명해봅시다.

• A와 D가 같은 경우
• A-B 경로와 D-E 경로의 일부가 겹치는 경우
• A-B 경로와 D-E 경로가 겹치지 않는 경우

 

A와 D가 같은 경우

A에서 가장 먼 노드는 B 입니다. 따라서 d1 > d2 입니다.
하지만 트리의 지름은 DE로 가정했기에 지름의 길이는 d2가 되지만, 지름은 두 노드 사이의 거리가 가장 긴 거리가 되어야 하므로 여기서 모순이 발생합니다.

 

단 d2 == d1인 경우에는 모순이 발생하지 않습니다. 이 경우는 지름이 두 개인 경우입니다.

 

 

 

A-B 경로와 D-E 경로의 일부가 겹치는 경우

A에서 B가 가장 멀기 때문에 AE > AB 입니다.
d1 + d5 + d3 > d1 + d5 + d4 이므로 d3 > d4 라고 할 수 있겠네요.

이때의 지름의 길이 DE = d2 + d5 + d4 입니다. 이 길이가 가장 긴 길이여야 하지만
d2 + d5 + d4 < d2 + d5 + d3 이기 때문에 모순이 발생합니다.

 

이 경우도 마찬가지로 d4 == d3 이어야 모순이 발생하지 않습니다.

 

 

 

A-B 경로와 D-E 경로가 겹치지 않는 경우

조건에 의해 AB > AD, AB > AE 이 성립합니다.
따라서 d1 + d2 > d1 + d5 + d3,  d1 + d2 > d1 + d5 + d4 입니다. =>  d2 > d5 + d3, d2 > d5 + d4
한 번 더 정리하면 d2 > d3, d2 > d4

 

이때 지름은 d3 + d4 입니다. 그런데 이 길이보다 더 긴 경우가 존재합니다. 
BD의 경우를 볼까요? d3 + d5 + d2 입니다. d2 > d4 이기 때문에 당연히 더 긴 거리입니다.

BE의 경우도 마찬가지로 모순이 발생합니다.

 

마찬가지로 d5 + d4 혹은 d5 +d3 == d2 인 경우에 모순이 발생하지 않습니다.

 

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n;
vector<vector<pair<int, int>>> graph; 

void dfs(int cur, vector<int>& dist)
{
    for (auto node : graph[cur])
    {
        int next = node.first;
        int nextDist = node.second;

        if (dist[next] != -1)
            continue;

        dist[next] = dist[cur] + nextDist;
        dfs(next, dist);
    }
}

pair<int, int> findFar(int start)
{
    vector<int> dist(n+1, -1);
    dist[start] = 0;
    dfs(start, dist);
    pair<int, int> ret = {0, 0};
    for (int i=1; i<=n; ++i)
    {
        if (ret.second < dist[i])
        {
            ret = {i, dist[i]};
        }
    }
    return ret;
}

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

    cin >> n;
    graph.resize(n+1);
    for (int i=1; i<=n; ++i)
    {
        int from;
        cin >> from;
        int dest, weight;
        while (true)
        {
            cin >> dest;
            if (dest == -1)
                break;
            cin >> weight;

            graph[from].push_back({dest, weight});
        }
    }

    pair<int, int> far = findFar(1);
    pair<int, int> ans = findFar(far.first);

    cout << ans.second << endl;

    return 0;
}

 

 

참고

https://johoonday.tistory.com/217