Algorithms/Tree Algorithms

2.18.2 Tree Diameter

개념

트리에서 가장 긴 경로

트리의 지름은 두 정점 사이의 거리 중 가장 큰 값입니다. 간선에 가중치가 있으면 경로에 있는 가중치의 합을 거리로 사용합니다.

가중치가 모두 00 이상인 트리에서는 두 번의 탐색으로 지름을 구할 수 있습니다.

  1. 임의의 정점에서 가장 먼 정점 AA를 구합니다.
  2. AA에서 가장 먼 정점 BB를 구합니다.
  3. AA와 BB 사이의 거리가 지름입니다.

두 탐색의 역할

가중치가 모두 11이고 간선이 (1,2),(2,3),(3,4),(2,5)(1,2),(2,3),(3,4),(2,5)인 트리를 보겠습니다. 22에서 가장 먼 정점은 거리 22인 44입니다. 하지만 22는 가장 긴 경로의 중간에 있으므로 이 거리 22가 지름은 아닙니다. 44에서 다시 탐색하면 11과 55까지 거리가 각각 33이고, 이것이 지름입니다.

첫 탐색은 시작점을 지름의 끝점으로 옮기는 역할을 합니다. 두 번째 탐색은 그 끝점에서 반대쪽 끝점까지의 길이를 구합니다. 가장 먼 정점이 여러 개이면 그중 하나를 선택할 수 있습니다.

가중치가 있어도 두 정점 사이의 경로가 하나이므로 DFS나 BFS로 그 경로의 간선 비용을 더하면 거리가 정해집니다. 모든 정점을 시작점으로 탐색하면 정점 수만큼 탐색해야 하지만, 이 방법은 두 번으로 줄입니다.

첫 탐색으로 지름의 끝점을 찾는 이유

이미 가장 긴 경로 하나를 골랐다고 생각하고 그 양 끝을 P,QP,Q라고 하겠습니다. 첫 탐색의 시작점은 SS, SS에서 가장 먼 정점은 AA입니다. 두 정점 사이의 거리를 dd로 나타냅니다.

SS에서 경로 P→QP\to Q에 처음 닿는 점을 XX, AA에서 처음 닿는 점을 YY라고 하겠습니다. 트리에는 사이클이 없으므로 각각의 갈래는 이 경로에 한 곳에서만 연결됩니다. P,QP,Q의 이름을 필요하면 서로 바꾸어 경로 위에서 P,X,Y,QP,X,Y,Q 순서가 되게 할 수 있습니다. 같은 위치인 점이 있어도 됩니다.

SS에서 QQ까지는 X,YX,Y를 지나갑니다. AA는 QQ보다 가깝지 않은 정점으로 골랐으므로 다음 관계가 성립합니다.

d(S,A)≥d(S,Q)=d(S,X)+d(X,Y)+d(Y,Q).d(S,A)\ge d(S,Q)=d(S,X)+d(X,Y)+d(Y,Q).

한편 SS에서 X,YX,Y를 거쳐 AA로 가는 이동의 길이는 실제 경로의 길이 이상입니다. 갈래 일부를 되짚어 지나가는 경우가 있어도 가중치가 00 이상이기 때문입니다. 따라서 다음과 같습니다.

d(S,A)≤d(S,X)+d(X,Y)+d(Y,A).d(S,A)\le d(S,X)+d(X,Y)+d(Y,A).

두 관계에서 공통 부분을 비교하면 d(Y,A)≥d(Y,Q)d(Y,A)\ge d(Y,Q)입니다. 따라서 가장 긴 경로 P→QP\to Q의 마지막 부분 Y→QY\to Q를 Y→AY\to A로 바꾸어도 길이가 줄지 않습니다. 원래 경로보다 더 긴 경로는 없으므로 P→AP\to A도 지름이고, AA를 지름의 끝점으로 사용할 수 있습니다.

복잡도

정점 수를 NN이라고 합니다.

연산시간복잡도공간복잡도
두 번의 탐색O(N)O(N)그래프·재귀 O(N)O(N)

예제

문제

간선에 길이가 있는 트리의 지름을 구하여라.

입력

첫째 줄에 정점 수 NN이 주어진다. 1≤N≤1001\le N\le100이다.

다음 N−1N-1개 줄에 간선의 양 끝점 a,ba,b와 길이 ww가 공백을 사이에 두고 주어진다. 1≤a,b≤N1\le a,b\le N; 1≤w≤1001\le w\le100이다.

출력

트리의 지름을 출력한다. 정점이 하나이면 00을 출력한다.

예제 입력

5
1 2 3
1 3 2
2 4 4
2 5 1

예제 출력

9

예제 코드

C++20

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

vector<pair<int, int>> g[101];
int far, best;

void dfs(int u, int par, int dist) {
    if (dist > best) {
        best = dist;
        far = u;
    }
    for (const auto& [v, w] : g[u]) {
        if (v == par) continue;
        dfs(v, u, dist + w);
    }
}

int main() {
    int n, i, a, b, w;

    cin >> n;
    for (i = 0; i < n - 1; ++i) {
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }

    far = 1;
    best = 0;
    // 임의의 정점에서 가장 먼 정점을 찾아 지름의 한 끝점 선택
    dfs(1, 0, 0);
    a = far;
    best = 0;
    // 찾은 끝점에서 다시 가장 먼 정점까지의 거리를 구해 지름 계산
    dfs(a, 0, 0);

    cout << best << '\n';
}