[백준] 4386번 별자리 만들기(파이썬, MST)

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

4386번: 별자리 만들기

이번 문제는 최소 스패닝 트리 문제였다.

kuruskal mst 알고리즘을 사용했다.

핵심은 간선간의 비용은 좌표 간의 거리이며 2차 평면에서 두 좌표의 거리는 직각삼각형을 그려서 빗변의 길이를 구하면 두 좌표간의 거리가 된다.

x1, y1 과 x2, y2 두 좌표가 있다면

|x1 - x2|^2 + |y1 - y2|^2

의 루트 값이 바로 두 좌표간의 거리가 된다.

 

import sys
import heapq
n = int(sys.stdin.readline())
parent = {}
graph = []

def find(x):
    if parent[x] == False:
        return x
    p = find(parent[x])
    parent[x] = p
    return p

def union(x, y):
    if parent[x] < parent[y]:
        parent[x] += parent[y]
        parent[y] = x
    else:
        parent[y] += parent[x]
        parent[x] = y


for _ in range(n):
    x, y = map(float, sys.stdin.readline().split())
    parent[(x, y)] = False
    graph.append((x, y))

arr = []

for i in range(n-1):
    a = graph[i][0]
    b = graph[i][1]
    for j in range(i+1, n):
        x = graph[j][0]
        y = graph[j][1]
        dx = abs(a-x)
        dy = abs(b-y)
        l = round((dx**2 + dy**2)**0.5, 2)
        heapq.heappush(arr, [l, (a, b), (x, y)])

cnt = n-1
answer = 0

while(cnt):
    l, a, b = heapq.heappop(arr)
    ar = find(a)
    br = find(b)
    if ar != br:
        union(ar, br)
        answer += l
        cnt -= 1
print(answer)

 

요로코롬 풀었다.