← 23주차 · 트리 DP와 문자열 매칭
보통트리DFS트리 DP

트리의 지름

정점 개수 n과 무방향 간선 목록 edges로 이루어진 트리가 주어져요. 트리에서 가장 먼 두 정점 사이 경로의 길이(지나는 간선 수)를 반환해요. 이 값을 트리의 지름이라고 해요.

핵심은 이거예요. 어떤 정점을 지나는 가장 긴 경로는, 그 정점에서 자식 방향으로 가장 깊게 내려가는 두 갈래를 더한 거예요. 모든 정점에서 이 값을 구해 가장 큰 것이 지름이에요.

DFS 한 번으로 끝나요. 각 정점은 '내 아래로 가장 깊은 깊이'를 부모에게 돌려주고, 그 과정에서 '가장 깊은 두 갈래의 합'으로 지름 후보를 갱신해요.

예시

예시 1
입력
n = 5, edges = [[0, 1], [1, 2], [1, 3], [3, 4]]
출력
3
설명
2 → 1 → 3 → 4 경로가 간선 3개로 가장 길어요.
예시 2
입력
n = 1, edges = []
출력
0
설명
정점이 하나뿐이라 경로 길이는 0이에요.

제한 사항

  • 1 ≤ n ≤ 50,000
  • edges.length는 n - 1이고, 그래프는 트리예요.
  • 0 ≤ a, b < n
depth(v, parent)가 v에서 아래로 내려가는 최대 간선 수를 돌려주게 해요. 자식들의 깊이 중 가장 큰 둘을 기억해 그 합으로 지름 후보(best)를 갱신하고, 부모에게는 '가장 깊은 하나 + 1'을 돌려줘요. 마지막 best가 지름이에요.
javascript
function treeDiameter(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) {
    adj[a].push(b);
    adj[b].push(a);
  }
  let best = 0;
  function depth(v, parent) {
    let first = 0;
    let second = 0;
    for (const next of adj[v]) {
      if (next === parent) continue;
      const d = depth(next, v) + 1;
      if (d > first) {
        second = first;
        first = d;
      } else if (d > second) {
        second = d;
      }
    }
    best = Math.max(best, first + second);
    return first;
  }
  depth(0, -1);
  return best;
}
이전 문제서브트리의 크기
다음 문제부분 문자열 찾기 (KMP)
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.