ALGORITHM/BOJ
[BOJ] 2887번 행성 터널 (C++)
yegyeom
2022. 1. 5. 13:40
문제 (https://www.acmicpc.net/problem/2887)
2887번: 행성 터널
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이
www.acmicpc.net
입력으로 행성들의 좌표가 들어온다. 이 좌표들로 모든 행성 사이의 거리와 연결 비용을 구한다면 시간 초과가 발생한다. (N ≤ 100,000)
따라서, 행성들의 x, y, z 좌표를 각각 정렬한 후 반복문을 돌며 각 좌표에서 인접한 행성들 간의 비용을 구한다. 예제와 같이 N이 5라면 총 12개의 간선 정보가 생성된다. N이 6이라면 15개이다. 즉 (N-1) * 3개의 간선 정보를 얻는 것이다.
이렇게 생성한 간선 정보를 오름차순으로 정렬한 후 크루스칼 알고리즘으로 최소 비용을 찾아내면 된다.
1) 입력
2) x, y, z 좌표를 각각 정렬한 결과
3) 각 좌표에서 인접한 행성들로 비용을 구한 결과 (출발 노드 번호 -> 도착 노드 번호 | 비용)
[소스코드]
