Willing

1. 문제 / 난이도 : Gold Ⅳ

www.acmicpc.net/problem/4386

2. 풀이 및 코드 설명

모든 노드를 이어야 한다 + 최소 비용 = 전형적인 MST 문제!

크루스칼 알고리즘을 사용해서 쉽게 풀 수 있었다. Union-Find 코드를 중간에 이상하게 틀려서 헤메긴 했지만... 조금 더 완벽히 숙지해야겠다.

간단한 코드이므로 블락 단위의 설명은 생략하겠음.

3. 전체 코드

import sys

#Union-Find
def find(x):
    if x == root[x]:
        return x
    else: return find(root[x])

def union(a, b):
    root_a, root_b = find(a), find(b)
    root[root_b] = root_a

N = int(input())
stars = [list(map(float, sys.stdin.readline().split())) for _ in range(N)]
root = [_ for _ in range(N)]
costs = {} #{(별1, 별2): distance} 형태의 딕셔너리(딱히 딕셔너리 아니어도 됨)

#모든 별들 간에 간선이 있다고 가정 => 비용 계산하여 저장
for i in range(N):
    for j in range(i+1, N):
        a = stars[i]
        b = stars[j]
        dist = round(((a[0] - b[0])**2 + (a[1] - b[1])**2)**0.5, 2)
        costs[(i, j)] = dist
#크루스칼 알고리즘을 위해 distance의 오름차순으로 정렬
costs = sorted(costs.items(), key = lambda x: x[1])

#크루스칼 알고리즘
answer = 0
while costs:
    current = costs.pop(0)
    a, b = current[0]
    cost = current[1]
    
    #같은 그룹에 있는 것이 아니라면
    if find(a) != find(b):
        answer += cost
        union(a, b)

print(answer)