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

📖 문제

4386번: 별자리 만들기

 

🔎 풀이

유니온 파인드를 활용하는 최소 신장 트리 문제입니다. 백준 1197번 최소 스패닝 트리와 비슷합니다. 해당 문제는 노드 사이의 거리가 간접적으로 주어진다는 점이 다릅니다. 별들의 2차원 좌표가 주어지기 때문에, 별들 사이의 거리를 우선적으로 구하면 됩니다. 아래 코드에서는 가장 간단한 유클리디안 거리를 이용했습니다.

 

💻 코드

import sys
input = sys.stdin.readline

# root를 찾는 함수
def find_parents(x):
    if parents[x] == x:
        return x
    return find_parents(parents[x])

# root를 통합하는 함수
def union_parents(a, b):
    a = find_parents(a)
    b = find_parents(b)
    if a < b:
        parents[b] = a
    else:
        parents[a] = b

# 두 점 사이의 거리를 계산하는 함수
def cal_dist(x1, y1, x2, y2):
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5


n = int(input())
parents = [int(x) for x in range(n)]
dist = []
stars = []

for _ in range(n):
    x, y = map(float, input().split())
    stars.append((x, y))

for i in range(n):
    for j in range(i+1, n):
        # 두 별 사이의 거리 계산
        k = cal_dist(stars[i][0], stars[i][1], stars[j][0], stars[j][1])
        # 거리, 출발 별, 도착 별
        dist.append((k, i, j))

# 최소 거리 순으로 나열
dist.sort()
ans = 0
for k, i, j in dist:
    # 두 별의 root가 같지 않다면 거리비용 추가하고 root 합치기
    if find_parents(i) != find_parents(j):
        union_parents(i, j)
        ans += k

print(ans)