[문제]

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

[코드]

import math
import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, x, y):
    a = find_parent(parent, x)
    b = find_parent(parent, y)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())
star = [[0.0, 0.0]]
for i in range(n):
    a, b = map(float, input().split())
    star.append([a, b])
parent = []
for i in range(n + 1):
    parent.append(i)

graph = []
for i in range(1, n + 1):
    for j in range(i + 1, n+1):
        distance = round(((star[i][0] - star[j][0]) ** 2 + (star[i][1] - star[j][1]) ** 2) ** (1 / 2), 2)
        graph.append([distance, i, j])

graph.sort()
result = 0.0
for i in graph:
    if find_parent(parent, i[1]) != find_parent(parent, i[2]):
        union_parent(parent, i[1], i[2])
        result += i[0]

print(result)

[풀이]

이 문제는 크루스칼 알고리즘을 이용한 최소 신장 트리 변형 문제다

먼저 별들의 좌표를 입력받고, 각 별에서 다른 별로의 거리를 구하여 graph를 만든다

이 후에는 크루스칼 알고리즘을 이용해 답을 구한다