[백준] 2887번: 행성 터널 - 파이썬

🔈 문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 $ N $개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 $ A(x_{A}, y_{A}, z_{A}) $와 $ B(x_{B}, y_{B}, z_{B}) $를 터널로 연결할 때 드는 비용은 $ min(\left|x_{A}-x_{B}\right|, \left|y_{A}-y_{B}\right|,\left|z_{A}-z_{B}\right|) $이다.
민혁이는 터널을 총 $ N-1 $개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

 

📝입력

 첫째 줄에 행성의 개수 $ N $이 주어진다. $ \left ( 1 \leq N \leq 100,000 \right ) $ 다음 $ N $개 줄에는 각 행성의 x,y,z 좌표가 주어진다.
좌표는 $ -10^{9} $보다 크거나 같고, $ 10^{9} $보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.

 

📑출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

 

📚 문제 풀이

모든 행성에 x, y, z 좌표가 주어진다.

행성 A에서 행성 B로 가는 터널의 비용이 $ min(\left|x_{A}-x_{B}\right|, \left|y_{A}-y_{B}\right|,\left|z_{A}-z_{B}\right|) $ 이면 A에서 다른 행성까지 가는 경로도 모두 확인해야 할까? 

대답은 아니다.

 

두 좌표의 차의 절대값을 최소로 하려면 정렬한 후 바로 앞에 있는 좌표랑 빼면 절대값을 최소로 할 수 있다.

때문에 A에서 다른 행성까지 가는 경로는 x,y,z로 각각 정렬했을 때 이웃한 것들을 뺀 절대값으로 경로를 두면 A에서 다른 행성으로 가는 모든 경로는 확인할 필요없다. 

 

그렇게 최소한의 경로만 담은 뒤 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 만들었다.

 

💻 코드

import sys, heapq
input = sys.stdin.readline
 
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent,parent[x])
    return parent[x]
 
 
def union_parent(parent,a,b):
    a = find_parent(parent,a)
    b = find_parent(parent,b)
 
    if a<b:
        parent[b] = a
    else:
        parent[a] = b
 
n = int(input())
all_path = []
sort_x = []
sort_y = []
sort_z = []
 
parent = [i for i in range(n)]
 
for i in range(n):
    x,y,z = map(int,input().split())
 
    heapq.heappush(sort_x, [x,y,z,i])
    heapq.heappush(sort_y, [y,z,x,i])
    heapq.heappush(sort_z, [z,x,y,i])
 
pre_x = heapq.heappop(sort_x)
pre_y = heapq.heappop(sort_y)
pre_z = heapq.heappop(sort_z)
 
for _ in range(n-1):
    aft_x = heapq.heappop(sort_x)
    aft_y = heapq.heappop(sort_y)
    aft_z = heapq.heappop(sort_z)
    
    heapq.heappush(all_path, [abs(pre_x[0]-aft_x[0]),pre_x[-1], aft_x[-1]]) # 가는 비용, i->j
    heapq.heappush(all_path, [abs(pre_y[0]-aft_y[0]),pre_y[-1], aft_y[-1]])
    heapq.heappush(all_path, [abs(pre_z[0]-aft_z[0]),pre_z[-1], aft_z[-1]])
    pre_x = aft_x
    pre_y = aft_y
    pre_z = aft_z
    
ans = 0
edges = 0
 
while all_path:
    cost, a,b = heapq.heappop(all_path)
    if find_parent(parent,a) != find_parent(parent,b):
        ans += cost
        union_parent(parent,a,b)
        edges += 1
    
    if edges==n-1:
        break
 
print(ans)

 

🍭 시행착오

 

틀렸던 이유는 find_parent() 함수 구현 부분에 실수가 있었다.

 

🔗 문제링크 행성 터널

2887번: 행성 터널