득이공간

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제풀이 N-1개의 에지를 구성하는 최소 비용을 구하는 MST 유형의 문제입니다. 각 에지의 비용을 구할 때, 모든 행성끼리 연결해버리면 O($N^{2}$)으로 시간초과가 발생합니다. 따라서 행성들을 X값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Y값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Z값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개)를 구합니다. 이렇게 되면 3N-3개의 에지만으로 문제를 풀 수 ..