Baekjoon 4386. 별자리 만들기 / Python

알고리즘 설명

문제 설명

모든 별을 잇는 최소 비용 구하기

코드 설명

최소신장트리를 찾는 문제이다.

1. 간선의 가중치를 기준으로 정렬
2. union-find 알고리즘을 사용해서 사이클이 없도록 간선을 추가
   시간 복잡도 : O(n ^ 2 log n)
   n의 최댓값이 100이므로, 충분히 효율적.

import sys
import math
input = sys.stdin.readline

# Union-Find (Disjoint Set) 구조 정의
def union_find(x):
    if parents[x] == x:
        return x
    parents[x] = union_find(parents[x])
    return parents[x]

def union_set(x, y):
    rootX, rootY = union_find(x), union_find(y)
    if rootX != rootY:
        if rank[rootX] < rank[rootY]:
            parents[rootX] = rootY
        elif rank[rootX] > rank[rootY]:
            parents[rootY] = rootX
        else:
            parents[rootY] = rootX
            rank[rootX] += 1


n = int(input())
star = [tuple(map(float, input().split())) for _ in range(n)]

# 간선과 거리 계산
line = []
for i in range(n):
    x1, y1 = star[i]
    for j in range(i + 1, n):
        x2, y2 = star[j]
        dist = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
        line.append((dist, i, j))

# 간선을 거리 오름차순으로 정렬
line.sort()

# Union-Find 자료구조 초기화
parents = list(range(n))
rank = [0] * n

# MST 알고리즘 실행
res = 0.0
for dist, u, v in line:
    if union_find(u) != union_find(v):
        union_set(u, v)
        res += dist

# 결과 출력
print(f"{res:.2f}")