BOJ 1967 트리의 지름

트리의 지름은 트리에 존재하는 모든 경로의 길이 중에서 가장 긴 경로이다.
그냥 간단히 다시 정리하면
트리의 지름은 트리에서 가장 긴 경로이다!

구하는 방법으로는 트리의 어떤 노드(아무 노드나 상관없음)에서 가장 멀리 있는 노드X를 찾고 그 노드X에서 가장 멀리 있는 노드Y를 찾으면 노드X에서 노드Y까지의 경로가 트리의 지름이다.

일단 이 것을 이해하려고 노력하기 전에 트리에 대해 내가 몰랐던 사실을 적어보려고 한다.
이 문제에서 트리는 사이클이 없는 무방향 그래프라고 나와있는데, 이 경우 사이클이 없는 무방향 그래프이므로 임의의 두 노드사이의 경로는 1개밖에 없다. 그렇기 때문에 그냥 경로를 찾으면 그것이 최단 경로이고, BFS로 최단 거리를 구할 수 있는 것이다.

그리고 트리의 지름은 두가지로 경우로 나눌 수 있는데 (종만북693페이지 참조)
1. 가장 긴 leaf node - leaf node
2. 가장 긴 root node - leaf node

이 이외의 경우는 즉 root 나 leaf가 아닌 내부노드에서 경로가 끝난다면 가장 긴 경로가 아니기 때문에 위의 두 가지 경우중 가장 긴 경로를 찾으면 된다.

자 이제, 트리의 지름을 구하는 방법으로 돌아와서...
트리의 지름의 양 끝 노드 중 하나의 노드만 알면 그 노드에서 가장 멀리 떨어진 노드를 찾으면 그것이 지름이 된다.(두 노드 사이의 경로는 1개밖에 없기 때문에)
그런데 문제는 트리의 지름의 양 끝 노드 중 하나를 어떻게 알아내느냐 이다.
바로 이것을 아무점에서나 시작해서 가장 멀리 떨어진 노드를 찾으면 구할 수 있다고 하는데, 즉 아무 점에서나 시작해서 가장 멀리 떨어진 노드가 트리의 지름의 양 끝 노드 중 하나라는 것인데, 이 부분을 증명해야 한다.

koosaga님이 블로그에 이것을 귀류법으로 증명을 해놓으셨는데, 여기에 간단히 정리하면,
일단 루트에서 가장 먼 노드 x가 트리의 지름의 한 끝 노드가 아닌 경우는 두가지로 나뉜다.
1. 루트 - x 경로가 트리의 지름과 트리의 지름의 양 끝 노드를 제외하고 일부가 겹치는 경우
2. 루트 - x 경로가 트리의 지름과 겹치지 않는 경우

트리의 지름의 양 끝 노드를 s, e라고 하면
1번, 2번 경우 모두 루트-x경로가 루트-s경로와 루트-e경로보다 크다는 것을 이용해서 트리의 지름보다 더 길이가 긴 경로가 있다는 것을 보일 수 있고 결국 모순이다. (그림을 그려보면 좀 더 이해하기 쉽다)

시간복잡도는 dfs를 두 번 하는데, 트리는 간선의 개수가 n-1개니까 O(4n)이 되어 O(n)인 것 같다.

참조 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략(구종만 저)(종만북)
      백준님 강의자료 트리1
       koosaga님 블로그
       sisobus님 블로그