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

얘는 직접 간선의 가중치를 만들어줘야 하는 문제.

각 정점을 1, 2, 3, ... 번 정점이라고 생각하고 그 둘을 잇는 거리를 구해서

다른 문제들과 마찬가지로 (정점1, 정점2, 가중치) 형태로 간선을 저장한 다음에 일반적인 최소신장트리 풀 듯 풀면 된다. 

from itertools import combinations
import sys
input = sys.stdin.readline
n = int(input())
edges = []
parent = [0] * (n+1)
for i in range(1, n+1):
    parent[i] = i

xy_ = [[0, 0]]
for _ in range(n):
    x, y = map(float, input().split())
    xy_.append([x, y])

# parent[i] = i, xy_[i] = [x, y]

pair_ = list(combinations([i for i in range(1, n+1)], 2))
for p1, p2 in pair_:
    edges.append((p1, p2, ((xy_[p1][0] - xy_[p2][0]) ** 2 + (xy_[p1][1] - xy_[p2][1]) ** 2) ** 0.5))

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

def union_node(a, b):
    a = find_parent(a)
    b = find_parent(b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

edges = sorted(edges, key = lambda x: x[2])
answer = 0