[백준][BOJ1185] 유럽여행

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

1185번: 유럽여행

---

2. 풀이 : Prim

---

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

---

4. 설명

예제를 그림으로 표현하면 그림[1]과 같다.

그림[1]

모든 나라를 N-1개의 길 만으로 방문해야 하며, 그때의 비용이 최소가 되어야 하므로 MST를 생성해야 함을 알 수 있다.

MST를 유지하며 시작 나라에서 모든 나라를 방문하고 시작 나라로 돌아오기 위해서는, 모든 도로를 2번씩 지나야 한다.

도로를 왕복하는 동안 도로의 양 끝의 나라는 1번씩 방문하게 되며, 예외로 시작 나라만 시작할 때 방문을 한 번 더 하게 된다.

각 도로의 비용을 (통행 비용 * 2) + 양 끝 나라의 방문 비용 으로 재정의하면 그림[2]와 같다.

그림[2]

재정의한 비용으로 MST를 생성하면 그림[3]과 같다.

그림[3]

MST의 특성상 임의의 나라에서 출발을 하더라도 동일하게 생성되므로, 시작 나라를 방문 비용이 가장 작은 나라로 선택한다.

그림[4]

그림[4]와 같이 4번 나라가 방문 비용이 가장 작으며, 이때 모든 나라를 방문하는 비용은 176으로 최소가 된다.

---

5. 코드