[백준 4386번] 별자리 만들기 문제 풀이 (with Python)

< 문제 >

 

 

< 입출력 >

 

< 풀이 >

크루스칼 알고리즘과 MST(최소 신장 트리) 알고리즘을 이용했다.

별자리들의 좌표를 입력받고, 그 별자리들 중 두개씩 골라 두 별사이의 거리를 계산해서 저장한다.

두 별사이의 거리가 작은 순으로 정렬한 후, 두 별의 루트 노드가 다르면 연결해준다.

 

 

< 코드 >

import sys
import math
input = sys.stdin.readline

def find(a):              # 루트 노드 찾기
    if a == parent[a]:
        return a
    parent[a] = find(parent[a])
    return parent[a]

def union(a, b):          # 두 노드 합치기
    a = find(a)
    b = find(b)
    if a < b:
        parent[a] = b
    if a > b:
        parent[b] = a

n = int(input())
star = []                 # 별의 x, y 좌표 배열
arr = []                  # 두 별의 인덱스와 두 별 사이의 거리 배열
result = 0
parent = [i for i in range(n)]   # 루트 노드
for _ in range(n):
    x, y = map(float, input().split()) 
    star.append((x, y))    # 각 별의 좌표 넣기

for i in range(n):
    for j in range(i+1, n):
        arr.append((i, j, math.sqrt((star[i][0]-star[j][0])**2 + (star[i][1]-star[j][1])**2)))  # 별i와 별j의 인덱스와 두 별 사이의 거리

arr.sort(key=lambda x : x[2])    # 두 별 사이의 거리가 작은순으로 배열

for x, y, dist in arr:
    if find(x) != find(y):       # 두 별이 연결되어 있지 않으면 연결
        union(x, y)
        result += dist

print("%.2f"%result)