백준 2887 - 행성 터널 (파이썬)

각 축별로 정렬을 한뒤에 거리를 구하면 i노드인 경우에 i + 1노드가 가장 최소거리에 있는 연결점인걸 알 수 있습니다.
즉 i + 2부터는 거리를 구할 필요가 없어져 간선의 수가 줄어듭니다.
이렇게 구한 간선들을 크루스칼 알고리즘을 사용해서 마저 연결했습니다.

import sys

input = sys.stdin.readline

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

def union(a, b, c):
    global result
    a = find(a)
    b = find(b)
    
    if a != b:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b
        result += c

def get_edges():
    for i in range(3):
        stars.sort(key = lambda x : x[i])
        for j in range(N - 1):
            tmp = abs(stars[j + 1][i] - stars[j][i])
            edges.append((tmp, stars[j + 1][3], stars[j][3]))
        
N = int(input())
parent = [i for i in range(N)]
stars = [list(map(int, input().split())) for _ in range(N)]
edges = []
result = 0

for i in range(N):
    stars[i].append(i)

get_edges()
edges.sort()

for cost, x, y in edges:
    union(x, y, cost)

print(result)