태그부터가 스포가 되는 문제.
하지만 스포도 못알아듣고 헤매기 쉬운 문제.
풀이를 해보겠다.

BOJ 2887 - 행성 터널 링크
(2022.09.29 기준 P5)
(치팅하면 이상한 행성으로 납치됨)

문제

N개의 행성이 있고, 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
그러면 모든 행성이 터널로 연결되게 한다면, 필요한 최소 비용

알고리즘

모든 행성을 연결되게 하는 최소 비용이므로 최소 스패닝 트리
그리고 풀이에서 자세히 후술할 좌표 정렬

풀이

행성의 개수는 N개고 각 행성은 (x, y, z) 좌표에 있다. 그러면 모든 행성을 다른 행성과의 비용을 계산한다면.. 메모리가 터진다.

그러면 어떻게 해야 할까?
행성끼리의 비용을 잘 살펴보면 min(각 축마다의 차이)이다. 즉, 축마다 살펴봤을 때, 가장 가까운 두 행성 말고는 연결할 가치가 없는 것이다. (제일 끝 두 행성은 한 행성만 연결된다.)
이해하기 쉽게 X축에 A, B, C 행성이 밑 그림처럼 있다고 생각해보자.

그러면 A-B, B-C 이렇게 이을 것이다. 왜냐면, 좌표 차이가 비용이 되기 때문.
A-C, B-C 이렇게 이으면 Cx - Bx 만큼의 비용 손해를 보게 되는 것이다.

이런 식으로 X, Y, Z축 모두 살펴보아야 하는 것이다.
결론은, 축마다 정렬해서 인접한 행성끼리 잇는 간선만 저장하면 된다.

다음은 평범하다. 간선을 가중치가 오름차순이 되게 정렬 후, union, find 함수를 이용해 MST를 만들면 된다.

코드

import sys; input = sys.stdin.readline

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

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

N = int(input())
pos = [list(map(int, input().split())) + [i] for i in range(N)] # 좌표와 행성 번호와 함께 저장

# 가중치는 min(x좌표의 차, y좌표의 차, z좌표의 차)
# 그러면 모든 행성을 이을 필요가 없고
# x, y, z 각 축별로 가까운 행성만 이어주면 된다.
# 그러므로 각 축별로 정렬하여 인접한 행성끼리 잇는 간선만 만들자.
edges = []
for k in range(3):
    pos.sort(key = lambda x: x[k])
    for i in range(N - 1):
        u = pos[i][3]
        v = pos[i + 1][3]
        w = pos[i + 1][k] - pos[i][k]
        edges.append([u, v, w])

parent = list(range(N)) # 부모 노드
answer = ct = 0
for u, v, w in sorted(edges, key = lambda x: x[2]): # 가중치가 오름차순이 되게 정렬
    if find(u) != find(v): # 부모 노드가 다르면 union
        union(u, v)
        answer += w
        ct += 1
        if ct == N - 1: # 연결된 간선의 개수가 N - 1개가 되면 MST 완성
            break
print(answer)

여담

이 문제는 정말 교육적인 문제다.
좌표 차이가 비용인 문제는 결국 정렬을 해야 한다는 교훈을 주기 때문.
앞으로도 종종 이런 문제가 있을 테니 잘 알아두자!