BOJ 2887 - 행성 터널

링크: https://www.acmicpc.net/problem/2887

모든 행성을 터널로 연결할건데, 그 비용의 합이 최소가 되게 만드는 최소 스패닝 트리 문제이다.

문제는 \(N\)이 너무 커서, 행성 사이의 간선을 전부 살피는 건 힘들다는 것이다.

두 행성 A와 B의 거리를 \(min(|x_A - x_B|, |y_A - y_B|, |z_A - z_B|)\) 로 정의했기 때문에 어떤 행성에서 가장 가까울 행성의 후보가 확 줄어든다.

행성 A에서 가장 가까운 행성 B는 \(|x_A - x_B|\)가 최소이거나 \(|y_A - y_B|\)가 최소이거나, \(|z_A - z_B|\)가 최소인 것 3개 중 하나이다.
\(x, y, z\)마다 정렬하면 된다.