[백준] 4386 - 별자리 만들기 (G4)

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

4386번: 별자리 만들기

문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다.

다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다.

물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다.

 

처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데,

혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다.

 

 

그리고 시간차이는 내장 자료형을 쓰는 편이 압도적으로 빨랐다...

 

import sys
input = sys.stdin.readline

def find(node):
    if parent[node] == node:
        return node

    parent[node] = find(parent[node])
    return parent[node]

def union(node1, node2):
    node1 = find(node1)
    node2 = find(node2)

    parent[node2] = node1


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

parent = [i for i in range(n)]

#print(stars)
edges = []

X, Y = 0, 1
for i in range(n):
    for j in range(n):
        if i == j:
            continue

        dist = ((stars[i][X] - stars[j][X]) ** 2 + (stars[i][Y] - stars[j][Y]) ** 2) ** 0.5

        edges.append((dist, i, j))

edges.sort(reverse=True)
edge_count, answer = 0, 0
while edges:
    dist, star1, star2 = edges.pop()

    if find(star1) != find(star2):
        answer += dist
        edge_count += 1
        union(star1, star2)
        if edge_count == n-1:
            break

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