[파이썬, Python] 백준 4386번 : 별자리 만들기

백준 4386번 : 별자리 만들기

(문제 바로가기)

 

 

내 코드

import sys

input = sys.stdin.readline


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


def union(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

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


n = int(input())    # 별의 개수
stars = [tuple(map(float, input().split())) for _ in range(n)]  # 별의 좌표 정보
dist = []   # 두개의 별 사이의 거리를 저장할 리스트


# 별 사이의 거리를 계산하여 dist에 저장
for i in range(n - 1):
    for j in range(i + 1, n):
        dist.append(
            (((stars[i][0]-stars[j][0])**2+(stars[i][1]-stars[j][1])**2)**0.5, i, j))

dist.sort()

answer, parent = 0, [i for i in range(n)]

for d, a, b in dist:
    if find_parent(parent, a) != find_parent(parent, b):
        union(parent, a, b)
        answer += d

print("{:.2f}".format(answer))