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

접근

별들 간의 거리를 가중치라고 두고 이 간선들을 모두 저장하여 kruskal MST 알고리즘을 이용하여 해결하였다.

MST 알고리즘 설명: 2021.05.02 - [코딩/백준 (Python)] - 백준 1197번: 최소 스패닝 트리 (Python)

백준 1197번: 최소 스패닝 트리 (Python)

처음에 별들이 주어지고, 별들을 순환하면서 각각 거리를 측정하여 [거리, 별1, 별2] 의 형식으로 저장해주었다. 거리 관련하여 이런식으로 모두 구하는 경우 대부분 시간초과가 되기 때문에 안될 줄 알았는데, 데이터가 작아서 그런지 통과되었다.

코드

import sys
import heapq


def distance(x, y):
    return ((x[0] - y[0]) ** 2 + abs(x[1] - y[1]) ** 2) ** 0.5


def find(x):
    if parent[x] < 0:
        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


n = int(sys.stdin.readline())
parent = [-1 for _ in range(n + 1)]
lines = []
stars = []
for i in range(n):
    a, b = map(float, sys.stdin.readline().split())
    stars.append([a, b])
for i in range(n - 1):
    for j in range(i + 1, n):
        d = distance(stars[i], stars[j])
        heapq.heappush(lines, [d, i, j])
cnt = n - 1
ans = 0
while cnt:
    d, a, b = heapq.heappop(lines)
    ar = find(a)
    br = find(b)
    if ar != br:
        union(ar, br)
        ans += d
        cnt -= 1
print(round(ans, 2))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!