행성터널 (크루스칼)

행성들의 거리의 최소값을 통해 크루스칼도 스패닝트리를 만들면됩니다.

다만 여기서 각 최소값은 x기준 정렬, y기준 정렬, z기준 정렬을 통해 만들 수 있고 각 인덱스를 따로 저장해줘야합니다.

 

 

import heapq

 

def find_parent(parent,x):

    if parent[x]!=x:

        parent[x]=find_parent(parent,parent[x])

    return parent[x]

 

def union_parent(parent,a,b):

    a = find_parent(parent,a)

    b = find_parent(parent,b)

    if a>b:

        parent[a]=b

    else:

        parent[b]=a

n = int(input())

 

parent = [0] *(n+1)

edges = []

x_lst = []

y_lst = []

z_lst = []

 

for i in range(n):

    parent[i] = i

 

for i in range(n): 

    x,y,z = map(int, input().split())

    x_lst.append((x,i))

    y_lst.append((y,i))

    z_lst.append((z,i))

 

x_lst.sort()

y_lst.sort()

z_lst.sort()

 

for i in range(n-1):

    edges.append((x_lst[i+1][0]-x_lst[i][0], x_lst[i+1][1], x_lst[i][1]))

    edges.append((y_lst[i+1][0]-y_lst[i][0], y_lst[i+1][1], y_lst[i][1]))

    edges.append((z_lst[i+1][0]-z_lst[i][0], z_lst[i+1][1], z_lst[i][1]))

 

edges.sort()

 

ln = len(edges)

answer = 0

 

for i in range(ln):

    v = edges[i][0]

    idx1 = edges[i][1]

    idx2 = edges[i][2]

    if find_parent(parent,idx1)!=find_parent(parent,idx2):

        union_parent(parent,idx1,idx2)

        answer+=v

 

print(answer)