트리의 지름 구하기

트리의 지름이란

트리의 지름 = 트리에서 가장 먼 두 노드(리프) 사이의 경로 길이

예를 들어, 아래와 같은 트리에서 트리의 지름은 4다. (6 → 5 → 2 → 1 → 3 경로)

        1
       / \
      2   3
     / \
    4   5
       / \
      6   7

접근 방법 1: DFS 재귀

트리의 지름을 구하는 가장 일반적인 방법은 DFS(깊이 우선 탐색)를 사용하여 각 노드에서의 최대 깊이를 계산하는 것이다.

알고리즘

1. 각 노드를 "경유점"으로 생각한다
2. 해당 노드를 지나는 최장 경로 = 가장 깊은 서브트리 깊이 + 두 번째로 깊은 서브트리 깊이
3. 모든 노드를 순회하며 최댓값을 갱신한다

핵심: 각 노드에서 자식 노드들 중 가장 깊은 두 개를 선택하여 합산한다. 이진 트리의 경우 자연스럽게 좌우 자식이 되고, 일반 트리에서는 모든 자식 중 상위 2개를 선택한다.

접근 방법 2: 2회 탐색

트리의 지름을 구하는 또 다른 방법은 임의의 노드에서 2번의 탐색을 수행하는 것이다.

알고리즘

1. 임의의 노드 A에서 BFS/DFS로 가장 먼 노드 B 찾기
2. 노드 B에서 다시 BFS/DFS로 가장 먼 노드 C 찾기
3. B와 C 사이의 거리 = 트리의 지름

왜 이 방법이 작동하는가?

트리는 사이클이 없는 연결 그래프이므로 다음 성질을 만족한다:

1. 첫 번째 탐색: 임의의 노드에서 가장 먼 노드는 항상 지름의 한 끝점이다

   • 트리에서 가장 먼 노드는 리프 노드
   • 그 리프 노드는 지름을 이루는 경로의 끝점 중 하나

2. 두 번째 탐색: 지름의 한 끝점에서 가장 먼 노드는 지름의 다른 끝점이다

   • 사이클이 없으므로 두 노드 사이의 경로는 유일
   • 이 경로가 곧 트리의 지름

정리

트리의 지름

• 트리에서 가장 먼 두 노드 사이의 거리
• 경로는 루트를 반드시 지나지 않아도 됨

해결 방법

핵심 포인트

• 두 방법 모두 O(N) 시간 복잡도로 효율적
• DFS 재귀: 깊이를 계산하면서 지름을 동시에 갱신
• 2회 탐색: 첫 번째 탐색으로 지름의 한 끝점을 찾고, 두 번째 탐색으로 다른 끝점을 찾음
• 문제 상황에 따라 적절한 방법을 선택하여 사용