백준 4386번 : 별자리 만들기 in Python

4386번: 별자리 만들기

 

www.acmicpc.net

이 문제는 2차원 평면 위의 별들을 이용해 별자리를 만들 때 선으로 연결된 별들의 거리의 합의 최소값을 구하는 문제이다.

즉, 이 문제는 최소 스패닝 트리를 구하는 문제이나 간선의 가중치가 직접적으로 주어지는 게 아니라 두 점 사이의 거리로 주어지는 경우이다. 그러므로 우선 각 점을 저장한 뒤에 모든 점들에 대해 두 점 사이의 거리를 구한 뒤 이를 두 점의 인덱스와 함께 저장한다. 그러면 나머지는 이전의 최소 스패닝 트리를 구하는 과정과 같다.

이를 코드로 구현하면 다음과 같다.

import sys
import math
import heapq
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

def find(u):
    if parent[u] == u: return u
    parent[u] = find(parent[u])
    return parent[u]
def union(u, v):
    root_u = find(u)
    root_v = find(v)
    parent[root_u] = root_v
n = int(input())
parent = [i for i in range(n+1)]
# 별의 좌표를 저장하는 배열. 각 별의 이름은 배열 내의 해당 별에 대응하는 인덱스로 한다.
stars = []
heap = []
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):
        # 두 점 사이의 거리를 구하되 round 함수를 이용해 소수점 둘째 자리까지 반올림해 나타낸다.
        dis = round(math.sqrt((stars[i][0] - stars[j][0])**2 + (stars[i][1] - stars[j][1])**2), 2)
        heapq.heappush(heap, [dis, i, j])
W = 0
while len(heap) > 0:
    w, u, v = heapq.heappop(heap)
    if find(u) != find(v):
        union(u, v)
        W += w
print(W)