[python] 백준 4386 별자리 만들기

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

4386번: 별자리 만들기

 

문제 해결

• 전형적인 유니온 파인드 문제
• 단 리스트 안에 두 별자리 간의 거리를 오름차순으로 정렬하고 연결 되어있는지 아닌지 유니온 파인드를 통해 확인하고 해결한다.

 

CODE

import sys
input = sys.stdin.readline
import math


def find(x):
    if x != parents[x]:
        return find(parents[x])
    return parents[x]

def union_parent(x,y):
    x = find(x)
    y = find(y)
    
    if x<y:
        parents[y] = x
    else:
        parents[x] = y

if __name__=="__main__":
    n = int(input())
    parents = [i for i in range(n+1)]
    stars = []
    edges = []
    result = 0
    
    for _ in range(n):
        x, y = map(float, input().split())
        stars.append((x,y))
    
    for i in range(n-1):
        for j in range(i+1,n):
            edges.append((math.sqrt((stars[i][0]-stars[j][0])**2 + (stars[i][1]-stars[j][1])**2), i, j))
    
    edges.sort()
    
    for edge in edges:
        cost, x, y = edge
        
        if find(x) != find(y):
            union_parent(x,y)
            result += cost
    print(round(result,2))