크루스칼
-
[백준 2887 - JAVA] 행성터널Algorithm 2020. 11. 9. 18:09
2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다! 간선을 찾고 MST로 연결하는 것은 쉽지만, 행성의 개수가 100,000개로 시간초과 혹은 메모리 초과가 발생하는 문제다. 나같은 경우에도 메모리 초과를 3번 겪고난 후 다른 블로그를 참고하여 문제를 해결했다. 풀이 방법 각 행성의 Index와 x, y, z를 저장하고 Union-Find에서 사용할 배열을 초기화한다. 행성들의 거리를 계산하여 간선으로 PQ에 삽입한다. ..