이번 문제는 유니온-파인드를 통해 해결하였다. 확실히 플레티넘 문제라 접근도 어려웠고, 혼자 풀는 것이 힘들었다... 결국은 다른 사람의 풀이를 참고해서 해결하였다. 원리는 가장 가까운 행성들을 우선적으로 찾는 것이었다. 그래서 z, y, x좌표를 각각 다른 리스트로 관리하고, 이를 이용해서 각 행성들간의 거리를 찾은 후, 이를 내림차순으로 정리하였다. 그리고 행성들 간의 거리를 저장한 리스트를 while문을 통해 pop하며 만약 a, b의 parent, 즉 연결 상태가 존재한다면 다음 반복으로 넘어가고 연결 상태가 없다면 둘을 union을 통해 연결시키고 정답 변수를 증가시키는 방법으로 해결하였다.

Code

def find(a):
    if a != parents[a]:
        parents[a] = find(parents[a])
    return parents[a]
def union(a, b):
    a = find(a)
    b = find(b)
    parents[b] = a
n = int(input())
zs, ys, xs = [], [], []
for i in range(n):
    z, y, x = map(int, input().split())
    zs.append((z, i))
    ys.append((y, i))
    xs.append((x, i))
zs.sort()
ys.sort()
xs.sort()
tmp = []
parents = [i for i in range(n+1)]
for idx in zs, ys, xs:
    for i in range(1, n):
        cost1, a = idx[i-1]
        cost2, b = idx[i]
        tmp.append((a, b, abs(cost1-cost2)))
tmp.sort(key=lambda x:x[2], reverse=True)
answer = 0
cnt = n-1
while cnt:
    a, b, cost = tmp.pop()
    if find(a) == find(b):
        continue
    union(a, b)
    cnt -= 1
    answer += cost
print(answer)