[BOJ] 1167번: 트리의 지름

www.acmicpc.net/problem/1167

 

임의의 노드를 root로 만든 후의 트리를 생각해봅시다.

이 트리는 정말 단순하게 생각하면

입니다. 이 때 A, B, 한 root로부터 subtree가 여러개 달려있다고 생각할 수 있습니다. 트리의 지름을 찾기 위해 가장 먼 두 node를 찾아야하는데, 두 node는 같은 subtree에 있거나 다른 subtree에 있을 것입니다.

i) 다른 subtree에 있을 경우
그 두 node를 잇는 경로 상에서 반드시 root를 거쳐가야합니다. 그러므로 subtree A에서 root로부터 가장 멀리 떨어진 점의 거리, subtree B에서 root로부터 가장 멀리 떨어진 점의 거리, subtree C에서 root로부터 가장 멀리 떨어진 점의 거리, subtree D에서 root로부터 가장 멀리 떨어진 점의 거리를 구해서 큰 값 2개를 더하면 됩니다. 이는 각 subtree에서 재귀적으로 처리해주면서 답을 알 수 있습니다.

ii) 같은 subtree에 있을 경우
i)번 과정에서 root로부터 가장 멀리 떨어진 점을 알아낼 때, 같은 subtree에 있는 경우를 재귀적으로 처리할 수 있습니다. 코드를 보면 이해가 될 것입니다.

구현은 root의 자식들 중에서 root와 가장 먼 것의 distance를 반환하는 longest_child(int root) 함수를 재귀적으로 계산하는 방식으로 이루어집니다.

github.com/encrypted-def/BOJ/blob/master/1167.cpp