4386_별자리만들기

https://www.acmicpc.net/status?user_id=supersfel&problem_id=4386&from_mine=1 

채점 현황

 

 

이역시 유니온파인드를 활용한 크루스칼 알고리즘을 활용하여 해결하였다.

 

 

처음에 각 별들의 좌표를 받는데, 이를 활용해서 각 별간의 거리를 모두 저장해주었다.

 

각 별들에게 1번,2번 .... 이름을 붙여주고

 

1-2 간의 거리 1-3번간의 거리... 를 반복해서 n-1,n번과의 거리까지 구해준다.

 

그 후 거리순으로 배열을 정렬해준 후에, 부모가 같지 않으면 두 집합을 합쳐준다.

 

import sys
input = sys.stdin.readline

n = int(input())
star=[]
for _ in range(n):
    x,y = map(float,input().split())
    star.append((x,y))

distance=[]
for i in range(n):
    for j in range(i,n):
        if i == j:
            continue
        dist = (( star[i][1] - star[j][1] )**2 + ( star[i][0]-star[j][0])**2)**0.5
        distance.append((i+1,j+1,dist))


parents=[i for i in range(n+1)]
def find(a):
    if a == parents[a]:
        return a
    parents[a] = find(parents[a])
    return parents[a]

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

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

distance.sort(key=lambda x : x[2])
result = 0
for a,b,c in distance:
    if find(a) != find(b):
        union(a,b)
        result += c
print(round(result,2))