안녕하세요,
재재입니다.
BOJ 8872 빌라봉 문제에 대한 풀이입니다.
BOJ 8872 빌라봉
(1) 문제 설명
분류 : graph, 트리의 지름
출처 : https://www.acmicpc.net/problem/8872
(100,000 이하) N개의 노드와
(100,000 이하) M개의 연결 정보가 들어옵니다.
모든 노드가 연결되어 있지 않은 포레스트 구조인데,
적절히 모든 노드를 연결 시켜서,
그 때의 트리의 지름의 최솟값을 구해주면 됩니다.
이때, 연결 시 코스트는 (1만 이하) L입니다.
(2) 풀이 도출
엣지 연결 시 트리의 지름을 최소로 하기 위해서,
다음과 같이 연결을 해야 합니다.
- 슈퍼 루트를 하나 정해서, 모든 포레스트는 슈퍼 루트에 직접 연결을 해야 한다. 여기서 답이 나오는 경우는 $$ r_s + r_x + L $$ 이 됩니다.
- 슈퍼 루트를 제외한 포레스트에서 답이 나오는 경우는 두 반지름에 L을 더한 $$ r_x + r_y + 2L $$이 됩니다.
- 그 외에는 모든 포레스트에서 정답이 나오는 경우입니다. 즉, 포레스트에서의 지름이 정답이 될 수 있습니다.
이렇게 3가지 경우를 제외한 답은 존재 할 수 없습니다.
이때, 슈퍼 루트의 후보군은 트리의 반지름이 가장 큰 포레스트의 루트입니다.
트리의 반지름은 지름을 구할 때와 같이 \( O(n+m) \)에 구할 수 있습니다.
또한, 반지름은 반드시 트리의 지름을 이루는 노드 집합 내에서 구할 수 있습니다.
포레스트에서의 루트를 정할 때는 가장 큰 반지름이 최소가 되는 노드가 후보군이 됩니다.
전체 시간복잡도 $$ O(n+m) $$에 해결 가능합니다.
BOJ 8872 빌라봉