[최소신장트리] 백준 4386번: 별자리 만들기 / 골드 4

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

4386번: 별자리 만들기

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일

www.acmicpc.net

import sys
import math
input = sys.stdin.readline

n = int(input())

starts = []
for i in range(n):
    a, b = map(float, input().split())
    starts.append([a, b])

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

graph = []
for i in range(n-1):
    for j in range(i+1, n):
        x1, y1 = starts[i]
        x2, y2 = starts[j]
        cost = (x2-x1)**2 + (y2-y1)**2
        graph.append([cost, i, j])
graph.sort()

def find(parent, x):
    if parent[x] == x:
        return x
    else:
        return find(parent, parent[x])

def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)

    if a > b:
        parent[a] = b
    else:
        parent[b] = a

answer = 0
for i in range(len(graph)):
    cost, a, b = graph[i]
    if find(parents, a) != find(parents, b):
        union(parents, a, b)
        answer += math.sqrt(cost)

print(answer)

max n = 100이기 때문에 완전탐색을 하면서 n2개 경우의 수를 모두 그래프에 담아도 시간 초과가 나지 않는다.