BOJ 8872 빌라봉

https://www.acmicpc.net/problem/8872

8872번: 빌라봉

이 문제는 아래의 세 가지 경우로 나누어 생각할 수 있다.

1. Forest에 트리가 한 개인 경우 -> 그 트리의 지름
2. Forest에 트리가 두 개 이상인 경우 -> 그리디 해법: 반지름이 가장 큰 트리의 중심 정점에 다른 모든 트리의 중심 정점을 연결하는 게 최적이다.
  a. 반지름이 가장 큰 트리와 두 번째로 반지름이 큰 트리를 연결한 것이 정답인 경우 (다리 한 개 사용)
  b. 두번째, 그리고 세 번째로 반지름이 큰 트리가 반지름이 가장 큰 트리의 중심 정점에 각각 연결된 경우가 정답인 경우 (다리 두 개 사용)
  c. 지름이 가장 큰 트리의 지름이 정답인 경우 (다리 사용 안 함)

위에서 어떤 트리의 중심 정점은, 트리의 한 정점을 선택해서 그 정점으로부터 다른 정점까지의 최대 거리를 최소로 하는 정점으로 정의한다. 이때 중심 정점으로 부터 가장 먼 정점까지의 거리를 트리의 반지름이라고 하자.

위의 과정까지는 어렵지 않게 생각할 수 있었다. 이제 문제는 각 트리의 지름과 반지름 (그리고 중심 정점)를 구하는 문제로 치환되었다.

트리의 지름(트리에서 임의의 두 점을 골랐을 때, 그 두 점 사이의 거리가 가장 긴 경우)을 구할 수 있으면, 트리의 중심은 지름을 이루는 경로상에 존재함은 어렵지 않게 증명할 수 있었다. 트리의 반지름은 트리의 중심에서부터 트리의 지름을 이루는 두 정점까지의 거리 중 더 긴 거리이다.

트리의 지름을 구하는 방법은 짱구를 열심히 굴려서 반 DP, 반 그리디 비슷하게 O(|V|)으로 어찌어찌 구현해서 AC를 받았는데, 다른 코드를 보다가 지름을 더 쉽게 구할 수 있다는 것을 알았다.

트리의 지름 구하는 방법 (O(|V|)):
1. 트리에서 임의의 정점을 선택해서 그 정점에서 가장 먼 정점을 찾는다. (dfs O(|V|))
2. 1번에서 찾은 정점으로부터 가장 먼 정점을 찾는다. (dfs O(|V|))
3. 1번과 2번에서 찾은 두 정점이 트리의 지름을 결정하는 두 정점이 된다.

증명을 직접 해보려 했으나 머리가 굳어서 되지가 않아, 구글 신의 도움을 받아 증명을 찾았다. 찾은 증명 중 가장 자세한 버전을 링크한다.

https://blog.naver.com/adamdoha/222121145206

19581번 : 두 번째 트리의 지름

https://jioneprogstdy.tistory.com/77

트리의 지름 증명