44_행성 터널 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 happenundo.tistory.com
행성터널
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 최소 신장 트리를 구하면 되는 문제이다. 하지만 이전 문제들보다 어려운 점이 있다면, 노드(행성)들 사이에 연결된 간선에 대한 정보가 주어져 있지 않다. 각 노드들의 좌표들만 주어져 있고, 두 노드의 좌표를 사용해 두 노드 간의 간선 비용을 구할 수 있다. 행성의 개수 N이 최대 10만개이므로 모든 노드의 거리를 구해서 크루스칼 알고리즘을 사용하려면 O(N(N+1) / 2)의 시간이 걸리고, 이는 무조건 시간 초과가 발생한다. 밑..
