[BOJ][Python] 백준 14950번 - 정복자

문제 링크: https://www.acmicpc.net/problem/14950

14950번: 정복자

---

문제 풀이

1번 도시를 반드시 포함하고 모든 도시를 포함하면서 최소 비용을 구해야 한다. 그래서 1번 도시에서 먼저 시작하면서 풀어야 할것 같지만 최소 신장 트리를 생각해보면 어짜피 최소 간선으로 모든 노드를 포함하므로 어디서 시작하던 1번 도시는 반드시 포함한다. 따라서 비용으로 정렬하여 구하면 된다. 또한 한번 union을 하게 되면 모든 간선이 t만큼 증가하게 되는데 MST는 노드가 n개 일때 n-1개의 간선을 가지므로 t*1+t*2+...+t*(n-2)만큼 증가하게 된다. 따라서 최소 신장 트리를 이용하여 최소 비용을 구하고 거기에 t*1+t*2+...+t*(n-2)을 더해주면 된다.

 

코드