트리의 지름이란?

---

"두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다."

출처: 백준 1967번: 트리의 지름

트리의 지름 구하기

---

순서

1. 임의의 정점 A에서 가장 먼 정점 B를 찾는다.
2. 정점 B에서 가장 먼 정점 C를 찾는다. 이때 B와 C 사이의 거리가 트리의 지름이다.

트리 가정

• 직관적으로 생각해보면 Leaf 노드에서 다른 Leaf 노드까지 중 가중치의 합이 가장 큰 것이 트리의 지름일 것이다.
• 직관적 생각을 바탕으로 Leaf 노드를 제외한 나머지 노드를 Root 노드라고 본다면 트리의 구조는 아래와 같다.

지름 구하기

• 앞의 가정에서 Leaf 노드를 제외한 노드를 Root 노드로 단순화하여 본다고 하였기에 임의의 노드를 Root로 정해보자. 이때 Root 노드는 1이다.
• 1. 임의의 정점 1에서 가장 먼 정점은 3이다.(1과 3의 가중치는 9)
• 2. 3에서 가장 먼 정점은 9이다.(3에서 9까지의 가중치는 17)
• 즉 트리의 지름은 17이다. 임의의 정점을 Leaf 노드로 설정한다고 해도 결과는 같다.