백준_4386_별자리 만들기

문제

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

4386번: 별자리 만들기

풀이

• 최소 스패닝 트리

https://en.wikipedia.org/wiki/Minimum_spanning_tree

Minimum spanning tree - Wikipedia

• Find Union

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0

서로소 집합 자료 구조 - 위키백과, 우리 모두의 백과사전

1. 모든 노드별 거리 값을 구한다.

2. cost가 작은 순으로 점을 연결한다.

3. 이미 연결된 점이라면, 다시 연결하지 않는다.

코드

import sys
input = sys.stdin.readline

N = int(input().strip())
starInfo = [list(map(float, input().strip().split())) for i in range(N)]

# edges별 거리 계산하기
def getValue(i, j) : 
    dx = starInfo[i][0]-starInfo[j][0]
    dy = starInfo[i][1]-starInfo[j][1]
    return (dx**2+dy**2)**0.5

edges = list()
for i in range(N) : 
    for j in range(i+1, N) : 
        value = getValue(i, j)
        edges.append((value, i, j))
edges.sort()

# find union
parent = [i for i in range(len(starInfo))]
def union(i, j) :
    if i==j : return
    i = find(i)
    j = find(j)
    
    if i>j : parent[i] = j
    else : parent[j] = i

def find(i) :
    if i==parent[i] : return i
    parent[i] = find(parent[i])
    return parent[i]


# calculate
answer = 0
for cost, i, j in edges : 
    if find(i) != find(j) : 
        union(i, j)
        answer += cost
        
print(round(answer, 2))