2887. 행성 터널

업데이트 시간 : 2023-04-04 07:38:02 +0000

[Platinum V] 행성 터널 - 2887

문제 링크

성능 요약

메모리: 91940 KB, 시간: 4840 ms

분류

그래프 이론, 정렬, 최소 스패닝 트리

문제 설명

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(x_A, y_A, z_A)와 B(x_B, y_B, z_B)를 터널로 연결할 때 드는 비용은 min(|x_A-x_B|, |y_A-y_B|, |z_A-z_B|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

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

출력

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

💡 Solutions

📄 행성 터널.py

N = int(input())

planet = []
for i in range(N):
    planet.append( (i,)+ tuple( map(int,input().split())) )
# Tree.sort(key = lambda x:x[0])
# print(planet)

px = [item[:] for item in planet]
px.sort(key=lambda x:x[1])

py = [item[:] for item in planet]
py.sort(key=lambda x:x[2])

pz = [item[:] for item in planet]
pz.sort(key=lambda x:x[3])

edges = []
# edge = ( distance, node1, node2 )
for i in range(len(px)-1):
    edge = ( abs(px[i+1][1] - px[i][1]) , px[i][0] , px[i+1][0]  )  
    edges.append( edge )
    
for i in range(len(py)-1):
    edge = ( abs(py[i+1][2] - py[i][2]) , py[i][0] , py[i+1][0]  )  
    edges.append( edge )
    
for i in range(len(pz)-1):
    edge = ( abs(pz[i+1][3] - pz[i][3]) , pz[i][0] , pz[i+1][0]  )  
    edges.append( edge )

edges.sort(key=lambda x:x[0])

parent = [i for i in range(N)]

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

answer= 0 
for w, s, e in edges:
    sRoot = find(s)
    eRoot = find(e)
    if sRoot != eRoot:
        if sRoot > eRoot:
            parent[sRoot] = eRoot
        else:
            parent[eRoot] = sRoot
        answer += w

print(answer)