BOJ 4386(별자리 만들기)풀이

solved.ac 티어 : 골드 4

www.acmicpc.net/problem/4386

4386번: 별자리 만들기

아주 간단한 mst문제이다. 점의 y, x가 주어지고 정점 개수-1개의 간선을 이어야 되니 모든 점을 이어준다. 이때 가중치는 두 점의 거리가 된다. 그러므로 두 점의 x좌표의 차 제곱 + 두 점의 y좌표 차 제곱을 루트 해준 값이

두 점 사이의 거리가 된다.

 

import sys,math
sys.setrecursionlimit(10**9)
def find(a):
    if uf[a]<0:return a
    uf[a]=find(uf[a])
    return uf[a]
def merge(a,b):
    a=find(a)
    b=find(b)
    if a==b:return 0
    uf[b]=a
    return 1
A=int(input())
l=[list(map(float,input().split())) for i in range(A)]
e=[]
up=0
for i in range(A):
    for g in range(i+1,A):
        e.append([math.sqrt(abs(l[i][0]-l[g][0])**2+abs(l[i][1]-l[g][1])**2),i+1,g+1])
        up+=1
e.sort()
rt=0
cnt=0
uf=[-1]*(201)
for i in range(up):
    if merge(e[i][1],e[i][2]):
        rt+=e[i][0]
        cnt+=1
        if cnt==A-1:break
print(format(rt,".2f"))