백준 4386 - 별자리 만들기 (파이썬)

좌표끼리의 거리를 계산하고 크루스칼 알고리즘을 사용해 해결했습니다.

import sys
import math

input = sys.stdin.readline

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

def union(a, b, c):
    global result
    a = find(a)
    b = find(b)
    
    if a != b:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
        result += c
        
n = int(input())
parent = [i for i in range(n + 1)]
stars = [list(map(float, input().split())) for _ in range(n)]
edges = []
result = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        edges.append((math.sqrt((stars[i][0] - stars[j][0])**2 + (stars[i][1] - stars[j][1])**2), i, j))
       
edges.sort()

for edge in edges:
    cost, x, y = edge
    union(x, y, cost)
    
print(round(result, 2))