트리의 지름 (Tree Diameter)

정의

트리의 지름 (Tree Diameter) 는 트리에서 가장 먼 두 노드 사이의 거리 (경로 길이). 가중치 없는 트리는 간선 개수, 가중치 트리는 간선 가중치 합.

대표 알고리즘:

1. 두 번 BFS/DFS: 임의 노드에서 가장 먼 노드 u 찾고, u 에서 가장 먼 노드까지 거리가 지름. O(N).
2. 트리 DP: 각 노드를 루트로 한 서브트리의 최장 경로 두 개를 합쳐 지름 후보. O(N).

문제 상황과 동기

“트리에서 가장 긴 경로” 가 필요한 상황.

• naive: 모든 노드 쌍 (u, v) 거리 계산. O(N^2). N=10^5 면 10^10.
• 두 번 DFS: O(N). 핵심: 트리에서 임의 노드 x 에서 가장 먼 노드는 지름의 한 끝점.
• 트리 DP: O(N). 각 서브트리에서 가장 긴 두 경로를 DP 로 관리.

핵심 통찰: 트리는 사이클이 없으므로, 지름의 두 끝점 중 하나는 임의 시작점에서 가장 먼 노드.

시각화

핵심 아이디어

두 번 BFS/DFS 방법

1. 임의 노드 x (보통 0) 에서 BFS/DFS → 가장 먼 노드 u.
2. u 에서 BFS/DFS → 가장 먼 노드 v.
3. dist(u, v) 가 지름.

증명 스케치: x 에서 가장 먼 노드 u 는 지름 경로의 끝점 중 하나거나, 지름 경로 밖 노드. 후자라면 지름 경로와 x-u 경로가 어딘가에서 만나는데, 그 교점에서 지름 끝점까지 거리가 x-u 보다 멀어야 하므로 모순.

트리 DP 방법

각 노드 u 에 대해:

• h[u] = u 를 루트로 한 서브트리에서 u 에서 시작하는 최장 경로.
• 자식 v 들의 h[v] 중 가장 긴 두 개를 합치면 u 를 지나는 최장 경로 → 지름 후보.

h[u] = max(h[v] + w(u, v))  for all child v
diameter = max(h[child1] + h[child2] + w(u, child1) + w(u, child2))

알고리즘

두 번 BFS

bfs(start):
    queue = [start], dist = {start: 0}
    while queue not empty:
        u = queue.pop()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                queue.push(v)
    return argmax(dist), max(dist)

find_diameter():
    u, _ = bfs(0)
    v, d = bfs(u)
    return d

트리 DP

dfs(u, parent):
    h[u] = 0
    top2 = [0, 0]            # 자식 중 가장 긴 두 경로
    for v in adj[u]:
        if v == parent: continue
        dfs(v, u)
        top2.append(h[v] + 1)
        top2.sort(reverse=True)
        top2 = top2[:2]
    h[u] = top2[0]
    diameter = max(diameter, top2[0] + top2[1])

find_diameter_dp():
    dfs(0, -1)
    return diameter

구현

// 두 번 BFS, O(N)
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[100005];
int N;
​
pair<int, int> bfs(int start) {
  vector<int> dist(N, -1);
  queue<int> q; q.push(start); dist[start] = 0;
  int farthest = start, maxDist = 0;
  while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v : adj[u]) {
          if (dist[v] == -1) {
              dist[v] = dist[u] + 1;
              q.push(v);
              if (dist[v] > maxDist) {
                  maxDist = dist[v];
                  farthest = v;
              }
          }
      }
  }
  return {farthest, maxDist};
}
​
int main() {
  cin >> N;
  for (int i = 0; i < N - 1; i++) {
      int a, b; cin >> a >> b; a--; b--;
      adj[a].push_back(b); adj[b].push_back(a);
  }
  auto [u, _] = bfs(0);
  auto [v, d] = bfs(u);
  cout << d << "\n";
}

# 트리 DP, O(N)
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline
​
N = int(input())
adj = defaultdict(list)
for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  adj[a].append(b); adj[b].append(a)
​
diameter = 0
​
def dfs(u, p):
  global diameter
  top2 = [0, 0]
  for v in adj[u]:
      if v == p:
          continue
      h_v = dfs(v, u)
      top2.append(h_v + 1)
      top2.sort(reverse=True)
      top2 = top2[:2]
  diameter = max(diameter, top2[0] + top2[1])
  return top2[0]
​
dfs(0, -1)
print(diameter)

// 두 번 DFS, O(N)
import java.util.*;
import java.io.*;
public class Main {
  static List<Integer>[] adj;
  static int N, maxDist, farthest;
​
  static void dfs(int u, int p, int d) {
      if (d > maxDist) {
          maxDist = d;
          farthest = u;
      }
      for (int v : adj[u]) {
          if (v != p) dfs(v, u, d + 1);
      }
  }
​
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      adj = new ArrayList[N];
      for (int i = 0; i < N; i++) adj[i] = new ArrayList<>();
      for (int i = 0; i < N - 1; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          int a = Integer.parseInt(st.nextToken()) - 1;
          int b = Integer.parseInt(st.nextToken()) - 1;
          adj[a].add(b); adj[b].add(a);
      }
      maxDist = 0; farthest = 0;
      dfs(0, -1, 0);
      int u = farthest;
      maxDist = 0;
      dfs(u, -1, 0);
      System.out.println(maxDist);
  }
}

5
1 2
2 3
3 4
4 5

4

복잡도

두 방법 모두 선형 시간, 가중치 트리도 간선 가중치만 바꾸면 동일.

변형 / 활용

함정

1. 루트 선택 무관하다는 착각

두 번 BFS 는 임의 노드에서 시작해도 되지만, 트리 DP 는 루트 선택이 구현 편의상 0 으로 고정해도 무방. 단, 지름 자체는 루트 무관.

2. 가중치 음수

일반 트리에서 음수 가중치 없지만, 문제에 따라 있을 수도. 두 번 BFS 는 가중치 음수 불가 (Bellman-Ford 필요). 트리 DP 는 음수 가중치도 처리 가능.

3. 1-indexed 입력

노드 번호 1-indexed 면 a--; b--; 필수.

4. 지름 경로 복원

지름의 길이만 아니라 경로 자체 필요하면, BFS 에서 parent 배열 기록 후 역추적.

BOJ 연습 문제

참고

• 최소 공통 조상
• 트리 DP
• 오일러 투어 테크닉