최소신장트리1 [백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번: 행성 터널첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이www.acmicpc.net 접근방법1. MST문제다. union-find 써야 할 것 2. 모든 행성 간 가중치를 구하려면 N! 인데? 3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다. 4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다. 5. 힙에 넣어 가중치 최솟값을 구한다면? 라고 생각회로 거쳤다. 정렬.. 2023. 5. 22. 이전 1 다음
