서로소집합
-
[백준] 2887번 행성 터널 (by Python)Programming/Algorithm 2021. 3. 13. 23:36
문제 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 풀이 문제를 보고 사이클을 생성하지 않는 범위 내에서 비용이 적은 순으로 edge를 (v - 1)개까지 선택하는 크루스칼 알고리즘이라는 걸 알 수 있다. 나는 처음에 min(|xA-xB|, |yA-yB|, |zA-zB|) 라고 제시된 각 edge의 비용을 모든 A와 B에 대해 계산하여 시간 초과를 마주하게 되었다. 그리고 좀 더 고민해본 결과 모든 좌표들의 x..