트리의 지름 (Diameter of Tree)

트리의 지름 (Diameter of Tree)

---

트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 트리의 지름이라고 한다. 이 트리의 지름을 가장 간단하게 구하는 방법은 다음과 같다.

1. 트리의 임의의 한 노드 \(u\)에서 가장 멀리 있는 노드 \(v\)를 찾는다.
2. \(v\)에서 가장 멀리 있는 노드 \(w\)를 찾는다.
3. \(v\) ~ \(w\)가 트리의 지름이 된다.

위의 방법에서 특정 노드에서 가장 멀리 있는 노드는 DFS나 BFS를 사용하면 쉽게 찾을 수 있다.

증명은 귀류법을 이용하여 \(v\) ~ \(w\)가 아닌 다른 두 노드 \(a\) ~ \(b\)를 트리의 지름이라고 가정한 후, 이것이 모순이 됨을 보이면 된다. (자세한 내용은 여기를 참고하자)

예제

• BOJ 1967 트리의 지름
  
• BOJ 2132 나무 위의 벌레

참고 자료

• http://koosaga.myungwoo.kr/entry/%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%A7%80%EB%A6%84-Diameter-of-tree
  
• http://cs.stackexchange.com/questions/22855/algorithm-to-find-diameter-of-a-tree-using-bfs-dfs-why-does-it-work