백준 14950번 정복자 파이썬

수 A, B, C가 주어진다. A와 B사이에 비용이 C인 도로가 있다는 뜻이다. A와 B는 N이하의 서로 다른 자연수이다. C는 10000 이하의 자연수이다.

출력

모든 도시를 정복하는데 사용되는 최소 비용을 출력하시오.

예제 입력 1

4 5 8
1 2 3
1 3 2
2 3 2
2 4 4
3 4 1

예제 출력 1

29

제출 답안

import heapq
import sys
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

n, m, t = map(int, input().split())
parent = [i for i in range(n+5)]
distance = []

def find_parent(x):
    if parent[x] == x:
        return x
    parent[x] = find_parent(parent[x])
    return parent[x]

def union(x, y):
    parent[find_parent(y)] = find_parent(x)
    find_parent(y)

for i in range(m):
    a, b, c = map(int, input().split())
    heapq.heappush(distance, (c, a, b))

answer = 0
i = 0

while distance:
    c, a, b = map(int, heapq.heappop(distance))
    if find_parent(a) != find_parent(b):
        union(a,b)
        answer += c + i*t
        i+=1

print(answer)

1. n,m,t를 받는다.
2. 부모리스트와 거리리스트를 만든다.
3. 공통부모 찾는 함수와 union 함수를 만든다.
4. 도시와 비용을 받는다.
5. 부모를 비교하여 다르면 길을 정복한것이니 연산을 수행한다.