[백준][BOJ1647] 도시 분할 계획

1. 문제 : https://www.acmicpc.net/problem/1647

1647번: 도시 분할 계획

---

2. 풀이 : Kruskal

---

3. 시간복잡도 : O(ElogE)

---

4. 설명

문제의 조건은 아래와 같다

1. 분리된 두 마을 사이의 길은 없앤다.

2. 각 분리된 마을 안에서 임의의 두 집 사이에 경로는 항상 존재하며, 길은 더 없앨 수 없다.

3. 길의 유지비의 합을 최소로 한다.

분리되기 전 하나의 마을에대해 MST를 생성한다. 완성된 MST에서 유지비가 가장 큰 길을 제거하면 길의 위의 3가지 조건을 만족하는 두 마을로 분리할 수 있다. kruskal 알고리즘으로 MST를 생성하면 가장 마지막에 추가되는 길이 유지비가 가장 큰 길이므로 쉽게 찾을 수 있다.

그림[1]

문제의 마을의 MST는 그림[1]과 같으며, 이 때 유지비의 최소값은 12이다.

그림[2]

그림[1]의 MST에서 가장 유지비가 큰 6번 집과 7번 집 사이의 길을 제거하면, 그림[2]와 같이 마을이 두 개로 분리되고 각 마을의 유지비는 최소가 된다.

---

5. 코드