[백준][Python] 4386 별자리 만들기

대놓고 MST문제이다. 간선위주고 거리값 구해서 heappush하고 최소 거리단위부터 잇고 이어져있으면 패스

안 이어진곳에서 최소 값을 heap을 통해 union하면서 거리값을 더해주는 kruskal로 해결.

prim은 아직 못한다..

import sys
input = sys.stdin.readline
from heapq import heappop,heappush

def kruskal():
    answer = 0
    while dists:
        ab_dists,star_a,star_b = heappop(dists)

        if find(star_a) !=find(star_b):
            answer += ab_dists
            union(star_a,star_b)
    return answer

def union(a,b):
    a = find(a)
    b = find(b)

    if a>b:
        parent[b] = a
    else:
        parent[a] = b

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

n=int(input())
# 거리가 최소가 되는 비용.
# 점을 다 연결한다.-> 간선 N-1 -> MST
matrix = [list(map(float,input().split())) for _ in range(n)]
parent = [i for i in range(n)]
dists = []
for i in range(n):
    for j in range(n):
        if i != j:
            heappush(dists,[round(((matrix[i][0] - matrix[j][0])**2 + (matrix[i][1] - matrix[j][1])**2)**0.5,2),i,j])


min_star_set = kruskal()

print(min_star_set)