robustflame의 블로그

트리의 지름 (Diameter of Tree) 트리에서 가장 멀리 떨어진 두 노드 사이의 길이를 트리의 지름이라고 한다. 이 트리의 지름을 가장 간단하게 구하는 방법은 다음과 같다. 트리의 임의의 한 노드 \(u\)에서 가장 멀리 있는 노드 \(v\)를 찾는다.\(v\)에서 가장 멀리 있는 노드 \(w\)를 찾는다.\(v\) ~ \(w\)가 트리의 지름이 된다. 위의 방법에서 특정 노드에서 가장 멀리 있는 노드는 DFS나 BFS를 사용하면 쉽게 찾을 수 있다. 증명은 귀류법을 이용하여 \(v\) ~ \(w\)가 아닌 다른 두 노드 \(a\) ~ \(b\)를 트리의 지름이라고 가정한 후, 이것이 모순이 됨을 보이면 된다. (자세한 내용은 여기를 참고하자) 예제BOJ 1967 트리의 지름 BOJ 2132 나..