[파이썬] 2887 행성 터널

import sys
input = sys.stdin.readline

def find_parent(x, parent):
    if x != parent[x]:
        parent[x] = find_parent(parent[x], parent)
    return parent[x]

def union_parent(a, b, parent):
    a = find_parent(a, parent)
    b = find_parent(b, parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

n = int(input())
li = [list(map(int, input().split())) + [i] for i in range(n)]

edges = []
for i in range(3):
    li.sort(key=lambda x: x[i])
    for j in range(1, n):
        edges.append((abs(li[j - 1][i] - li[j][i]), li[j - 1][3], li[j][3]))

parent = list(range(n))
ans = 0
for e in sorted(edges):
    if find_parent(e[1], parent) != find_parent(e[2], parent):
        union_parent(e[1], e[2], parent)
        ans += e[0]
print(ans)

MST, 크루스칼