728x90 크루스칼1 [python] 백준 2887 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 해결 최소 거리를 측정해야하는데 각 축에서 가장 차이가 작은 값으로 거리를 정의한다. 축을 분리해서 정렬 후 (오름차순) 거리차를 계산하는 것은 짐작할 수 있다. 그 후 점을 연결시키는데 이미 연결 되어있으면 넘어가고 아니면 점을 연결하고 비용을 추가해준다. 연결 되어있고 아니고를 유니온-파인드(Union-find)를 통해 계산한다. 이와 같은 방법을 크루스칼.. 2024. 2. 24. 이전 1 다음 728x90
