별자리 만들기

1. 개요

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

2. 풀이

import math, sys

def solution():
    INPUT = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(INPUT())
    READFLOATLIST = lambda: list(map(float, INPUT().split()))

    N = READINT()
    P = [n for n in range(N)]
    STARS = [READFLOATLIST() for _ in range(N)]
    EDGES = []

    def driver():
        edges()
        return kruskal()

    def kruskal():
        result = 0
        
        for d, a, b in EDGES:
            if not union(a,b):
                continue

            result += d
        return round(result, 2)

    def union(a, b):
        pa, pb = parent(a), parent(b)
        
        if pa==pb:
            return False
        elif pa>pb:
            P[pb] = pa
        else:
            P[pa] = pb
        return True
            
    def parent(a):
        if P[a]!=a:
            P[a] = parent(P[a])
        return P[a]

    def edges():
        for i in range(N):
            for j in range(N):
                if i==j:
                    continue
                EDGES.append((distance(i, j), i, j))
        EDGES.sort()
    
    def distance(i, j):
        return math.sqrt(
            (STARS[i][0] - STARS[j][0])**2 + (STARS[i][1] - STARS[j][1])**2)
        

    return driver()

print(solution())