[백준 - Python] 14950 - 정복자

0.  문제 링크

 

 

https://www.acmicpc.net/problem/14950

14950번: 정복자

---

1.  풀이 방법

 

전형적인 MST 문제

프림과 크루스칼 중 뭐로 풀까 고민했다.

시작은 프림으로 했는데, 이유는 시작 도시가 1번 도시이므로 1번부터 정점에 넣어서 MST를 탐색하는게 맞다고 생각했다.

근데 내 구현 issue로 인해, 엄청난 시간초과가 나버렸다...

 

그래서 결국 크루스칼 알고리즘으로 문제를 풀었다.

생각해보니까 어차피 MST면 1번 정점을 포함하니까,,,,뭐 그냥 크루스칼로 풀어도 될 것 같다는 느낌?

그래서 그냥 크루스칼로 풀었다.

결론은 크루스칼로 풀면 된다는 점!

추가로 방어태세를 갖춰서 비용이 올라가는거는 그냥 처음에 구해놓으면 된다.

어차피 n - 1개의 엣지를 구해야하니까, 비용은 n - 2번 올라간다고 생각하면 쉽게 구할 수 있다.

그리고 엣지는 n - 1번만 반복해서 구하면 된다. 추가로 하는건 쓸데없음

 

참고로 union에서 모든 자식의 부모를 바꾸는 과정도 추가했는데, 해당 과정이 없으면 시간이 압도적으로 늘어난다.

시간이 짧은건 모든 자식의 부모를 바꿔줬을 때고, 시간이 긴건 최상위 노드의 부모만 바꿔줬을 때이다...

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


def my_par(x):      # 내 부모를 찾음
    while x != par[x]:
        x = par[x]
    return x


def union(x, y):        # 합침
    par_x = my_par(x)
    while y != par[y]:
        temp, y = y, par[y]
        par[temp] = par_x
    par[y] = par_x


if __name__ == "__main__":
    n, m, t = map(int, input().split())
    ans = (n - 2) * (n - 1) * t // 2
    par = [*range(n + 1)]
    maps = []

    for _ in range(m):
        a, b, c = map(int, input().split())
        heapq.heappush(maps, [c, a, b])

    i = 0
    while i < n - 1:
        c, a, b = heapq.heappop(maps)
        if my_par(a) != my_par(b):
            union(a, b)
            ans += c
            i += 1

    print(ans)

---

3.  마무리