행성 터널

시간 제한1초메모리 제한128 MB

요약
3차원 좌표의 N개 행성 사이에서 두 점의 최소 축 거리를 비용으로 삼아 모든 행성을 연결하는 최소 스패닝 트리 비용을 구합니다.
난이도

어려움10점 중 8점

유형
최소 신장 트리, 정렬, 유니온 파인드
정답자
아직 제출이 없습니다

문제

때는 2040년, 민혁이는 우주에 NN개의 행성으로 이루어진 자신만의 왕국을 세웠다. 민혁이는 행성들을 효율적으로 다스리기 위해 행성을 잇는 터널을 건설하려고 한다.

각 행성은 3차원 좌표 위의 한 점으로 생각한다. 두 행성 A(xA,yA,zA)A(x_A, y_A, z_A)와 B(xB,yB,zB)B(x_B, y_B, z_B)를 터널로 잇는 비용은 min⁡(∣xA−xB∣, ∣yA−yB∣, ∣zA−zB∣)\min(|x_A - x_B|,\ |y_A - y_B|,\ |z_A - z_B|)이다.

민혁이는 터널을 정확히 N−1N-1개 지어 모든 행성이 서로 연결되게 하려고 한다. 모든 행성을 터널로 연결하는 데 드는 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 NN이 주어진다 (1≤N≤100 0001 \le N \le 100\,000). 다음 NN개의 줄에는 각 행성의 xx, yy, zz 좌표가 주어진다. 좌표는 −109-10^9 이상 10910^9 이하의 정수이다. 한 위치에 행성이 둘 이상 있는 경우는 없다.

출력

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

예제1

  1. 예제 1

    입력
    5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
    예상 출력
    4