2887번: 행성 터널 www.acmicpc.net 이 문제는 행성 간의 터널을 만들어 모든 행성들을 연결하고자 할 때 드는 비용의 최솟값을 구하는 문제이다. 이 때 각 행성의 위치는 3차원 좌표로 나타내고 두 행성 간 터널 건설 비용은 두 행성의 x좌표, y좌표, z좌표의 차이 중 가장 작은 값이다. 만약 행성의 개수가 적은 경우, 이전의 별자리 만들기 문제처럼 모든 행성 간의 터널 건설 비용을 구한 다음 가장 적은 비용의 터널부터 순차적으로 추가해 나가면 된다. 그러나 이 문제는 행성의 개수가 최대 10^5개까지 가능하기 때문에 이러한 방식으로 문제를 해결하려 하면 매우 오랜 시간이 소요된다. 그러므로 이보다 더 효율적으로 문제를 해결할 방법을 찾아야 한다. 백준 4386번 : 별자리 만들기 in P..
