[BOJ] 4386번 : 별자리 만들기(Kruskal, MST)

목차

접근

최소 스패닝 트리를 구하고, 그 비용을 구하는 문제다.

문제 자체는 간단하기에 크루스칼 알고리즘을 이용해서, 쉽게 해결했다.

 

해결

각 별 사이들간의 거리를 미리 다 구해놓고, 연결된 별과 그 거리를 저장해준다.

또 거리를 기준으로 오름차순 정렬을 수행한 뒤, 크루스칼 알고리즘을 수행한다. 

크루스칼 알고리즘은 Union-Find 알고리즘을 수행하는데, 해당 내용은 이전 아티클을 참고하자.

2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal)

 

코드

n = int(input())
coords = []
edges = []
for _ in range(n):
    a, b = map(float, input().split())
    coords.append((a, b))
    
for i in range(n):
    for j in range(i+1, n):
        w = ((coords[i][0] - coords[j][0])**2 + (coords[i][1] - coords[j][1])**2) ** 0.5
        edges.append((w, (i, j)))
        
edges = sorted(edges, key=lambda x : x[0])
parents = [i for i in range(n)]

def find(x):
    if parents[x] == x:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]
    
def union(x, y):
    x = find(x)
    y = find(y)
    parents[y] = x
    
    
dist = 0
e_num = 0
for w, (a, b) in edges:
    if e_num == n-1:
        break
    
    if find(a) != find(b):
        dist += w
        e_num += 1
    
    union(a, b)

print(f"{dist:.2f}")