문제
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
| 5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19 | 4 |
풀이
이 문제는 메모리 관리가 주요 핵심인 문제이다.
일반적인 크루스칼 문제와 크게 다르지 않지만, 정점의 개수가 100,000개 까지 존재하기 때문에 모든 간선의 경우의 수를 체크할 경우 메모리 초과가 발생한다.
따라서, 불필요한 경로를 최대한 줄이는 방법을 구상해야 한다.
우선 행성간의 거리를 구하는 방법은 세가지가 존재한다.
- X 좌표 사이의 거리
- Y 좌표 사이의 거리
- Z 좌표 사이의 거리
이렇게 세가지의 거리 중 가장 작은 것으로 행성들을 연결시켜주면 된다.
즉 X, Y, Z 를 따로 관리하여 행성간의 최단 거리를 구해야 한다.
각각의 배열들을 오름차순으로 정렬하면, 최단 거리는 당연히 바로 다음 행성이 될 것이다.
즉 i번째 행성에서 가장 가까운 행성은 i+1 번째 행성이 되는 것이다.
그러면 우리는 행성 끼리의 모든 간선을 체크할 필요가 없어지게 된다.
이후 간선들을 min_heap 으로 생성하여 크루스칼 알고리즘을 진행한다.
코드
from sys import stdin
from heapq import heappop, heappush
input = stdin.readline
def find(root, v):
if root[v] == v:
return v
else:
root[v] = find(root, root[v])
return root[v]
def union(root, A, B):
A = find(root, A)
B = find(root, B)
if A < B:
root[B] = A
else:
root[A] = B
def solution():
N = int(input())
root = [i for i in range(N + 1)]
planets = [tuple(map(int, input().split())) for _ in range(N)]
answer = 0
X = []
Y = []
Z = []
for i in range(N):
X.append((planets[i][0], i + 1))
Y.append((planets[i][1], i + 1))
Z.append((planets[i][2], i + 1))
X.sort()
Y.sort()
Z.sort()
pq = []
for i in range(N - 1):
heappush(pq, (abs(X[i][0] - X[i + 1][0]), X[i][1], X[i + 1][1]))
heappush(pq, (abs(Y[i][0] - Y[i + 1][0]), Y[i][1], Y[i + 1][1]))
heappush(pq, (abs(Z[i][0] - Z[i + 1][0]), Z[i][1], Z[i + 1][1]))
cnt = 0
while cnt < N - 1:
cost, S, E = heappop(pq)
if find(root, S) == find(root, E):
continue
union(root, S, E)
cnt += 1
answer += cost
print(answer)
solution()
