[Baekjoon] 4386번 : 별자리 만들기 (Python, 최소 신장 트리)

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

Contribute to stellaluminary/Baekjoon development by creating an account on GitHub.

github.com

Python

방법 1 - 메모리 32952KB / 시간 80ms / 코드 길이 708B

본 문제는 최소 신장 트리로 별은 node 그리고 이어지는 일직선은 edge이다.

이에 따라 거리에 대한 최소 비용을 구하는 것으로 최소 신장 트리가 적합하다.

크루스칼 알고리즘 , 프림 알고리즘 두 방법이 존재하는데 방법 1에서는 크루스칼 알고리즘을 활용하여 표현한다.

프림 알고리즘을 사용하고 싶다면 heapq를 사용해야한다.

유의 x, y는 실수이므로 float로 받아야한다.

나머지는 일반적인 최소 신장 트리와 같다.

import sys
import math

input = sys.stdin.readline

def f_p(p, x):
    if p[x] != x:
        p[x] = f_p(p, p[x])
    return p[x]

def union(p, a, b):
    a = f_p(p, a)
    b = f_p(p, b)
    if a < b:
        p[b] = a
    else:
        p[a] = b

n = int(input())
p = [i for i in range(n+1)]

edges = []
coord = []
res = 0

for _ in range(n):
    x, y = map(float, input().split())
    coord.append((x,y))

for i in range(n-1):
    for j in range(i+1, n):
        edges.append((math.sqrt((coord[i][0] - coord[j][0])**2 + (coord[i][1] - coord[j][1])**2), i+1, j+1))

edges.sort()

for edge in edges:
    c, a, b = edge
    if f_p(p, a) != f_p(p, b):
        union(p, a, b)
        res += c

print(round(res, 2))