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

https://www.acmicpc.net/problem/4386

4386번: 별자리 만들기

---

• 노드들이 각자 최소한으로 연결되면서 최소한의 거리를 가져야 한다.
• 모든 노드들에 대해 서로의 거리를 계산할 수 있기 때문에, 전체 그래프에서 가능한 에지와 거리를 우선순위 큐로 저장한다.
• Min Heap 을 사용하여 가장 짧은 거리를 가지는 노드들을 순서대로 연결시켜준다.
• 이 때 이번 에지를 추가함으로써 그래프에서 순환이 생길 경우엔 굳이 연결시킬 필요가 없기 때문에 제외한다.
• 그래프의 순환은 유니온파인드로 두 노드를 탐색하여 검사해준다.
• 찾아보니 이게 최소 스패닝 트리를 구하기 위한 크루스칼 알고리즘이라고 한다. 혼자 생각했다니 괜히 뿌듯하기도..

---

import heapq

def dist(X, Y):
    return ((X[0] - Y[0])**2 + (X[1] - Y[1])**2) ** 0.5

def find_(x):
    global parent
    if parent[x] == -1:
        return x
    parent[x] = find_(parent[x])    # path compression
    return parent[x]

def union_(x, y):                   # 유니온파인드
    global parent
    x = find_(x)
    y = find_(y)
    parent[x] = y

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

distances = [(dist(stars[i], stars[j]), (i,j)) for i in range(n) for j in range(i+1, n)]
heapq.heapify(distances)                    # 가능한 에지들에 대하여 모두 거리를 기준으로 정렬(중복 제거)

answer = 0
parent = [-1] * n

while len(distances):                       # 에지들을 짧은 연결 순서대로 검사하면서 (크루스칼)
    d, (x, y) = heapq.heappop(distances)
    if find_(x) != find_(y):                # 순환 구조가 이루어지지 않는다면 (유니온파인드로 검사)
        union_(x, y)                        # 두 노드를 연결해줌
        answer += d

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