문제

[백준] 별자리 만들기 (Gold 3)

요약

n개의 별들을 직선으로 이어 별자리를 만든다. 단, 사이클이 생기지 않도록 한다. 선을 하나 이을 때마다 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 비용을 구하라.

분류

  • 최소 스패닝 트리

풀이

내 풀이 (최소 스패닝 트리)

N개의 정점을 사이클이 생기지 않도록 N-1개의 간선으로 이어야 한다는 조건을 보고, MST를 떠올려야 했다.

import sys
input = sys.stdin.readline

n = int(input())
stars = [tuple(map(float, input().split())) for _ in range(n)]
edges = []
for i in range(n - 1):
    for j in range(i + 1, n):
        edges.append((i, j, (abs(
            stars[i][0] - stars[j][0]) ** 2 + abs(stars[i][1] - stars[j][1]) ** 2) ** 0.5))

edges.sort(key=lambda x: x[2])

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


def find(idx):
    global parent
    while parent[idx] != idx:
        idx = parent[idx]

    return idx


def union(s1, s2):
    if s1 < s2:
        parent[s1] = s2
    else:
        parent[s2] = s1


ans = 0
for v1, v2, dist in edges:
    s1 = find(v1)
    s2 = find(v2)

    if s1 != s2:
        ans += dist
        union(s1, s2)

print(ans)