백준 16398 : 행성 연결 (Python)

본문 링크

import sys
input=sys.stdin.readline

def Find(x):

    if x!=disjoint[x]:
        disjoint[x]=Find(disjoint[x])
    return disjoint[x]

N=int(input())

edge=[] ; disjoint=[ _ for _ in range(N+1) ] ; total=0

for i in range(N):

    L=list(map(int,input().split()))

    for j in range(N):
        edge.append( (L[j] , i+1,j+1) )

edge.sort(key=lambda x:x[0])

for value,x,y in edge:

    x=Find(x)
    y=Find(y)

    if x!=y:
        if x>y:
            disjoint[x]=y
        else:
            disjoint[y]=x
        total+=value

print(total)

📌 어떻게 접근할 것인가?

처음에 입력이 헷갈렸는데 그냥 모든 정점들에 대해서 연결해주면 됩니다. 다만 좌표들의 위치가 2차원 좌표로 주어지므로 프림 알고리즘보다 간선만 생각하면 되는 크루스칼 알고리즘을 사용했습니다.