[백준][BOJ14950] 정복자

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

14950번: 정복자

---

2. 풀이 : Prim

---

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

---

4. 설명

문제의 조건은 다음과 같다.

1. 처음 점거하고 있는 도시는 1번 도시이다.

2. 한번 정복한 도시는 다시 정복하지 않는다. 

3. 도시를 정복한 후에는, 정복한 도시의 수 만큼 추가 비용이 발생한다. 

4. 모든 도시를 최소의 비용으로 정복한다. 

1, 2, 4 조건에 의해 1번 도시를 시작점으로하는 MST를 생성하고, MST를 생성하는 과정에서 정복한 도시의 수 만큼 추가 비용을 더해준다.

그림[1]

그림[1]은 처음 시작하는 1번 도시만 정복한 상태를 표현

그림[2]

그림[2]에서 최소 비용으로 도시를 정복하기 위해 3번 도시를 정복하고, 나머지 도시들에는 추가 비용이 발생한다.

그림[3]

그림[3]에서 최소 비용으로 도시를 정복하기 위해 4번 도시를 정복하고, 나머지 도시들에는 추가 비용이 발생한다.

그림[4]

그림[4]에서 최소 비용으로 도시를 정복하기 위해 2번 도시를 정복하고, 나머지 도시들에는 추가 비용이 발생한다.

그림[5]

그림[5]에서 더 이상 정복할 도시가 없으므로 정복을 종료하며, 이 때 모든 도시들을 정복한 최소 비용은 2 + (1 + (1 * 8)) + (2 + (2 * 8)) 이 되므로 29가 된다.

---

5. 코드