[백준] No.2887 - 행성 터널 (C++, 크루스칼 MST)

문제

 

https://www.acmicpc.net/problem/2887

2887번: 행성 터널

 

풀이

 

solved.ac 난이도: Gold 1

 

단순한 최소 스패닝 트리 알고리즘의 적용으로는 해결할 수 없는 문제.

 

모든 행성을 연결하는 최소 비용을 구해야 하므로 최소 스패닝 트리(MST, Mininum Spanning Tree)를 구해야 한다.

간선의 정보는 직접 주어지지 않고  행성(정점)들의 위치를 통해 계산해야 하는데 모든 행성끼리 서로 간선을 잇게 되면

행성의 최대 개수 N(<= 100,000)이 너무 크다.

따라서 이번 문제는 최소 스패닝 트리에 속할 수 있는 간선만 생성하는 것이 중요하다.

 

두 행성 간의 터널은 서로의 행성을 직접적으로 잇는 것이 아닌, x, y, z 좌표의 차이 중에 가장 짧은 좌표를 직선으로 잇는다.

w(u, v) = min(|Xu - Xv|, |Yu - Yv|, |Zu - Zv|)

 

그러므로 x, y, z 좌표계를 각각 독립적으로 생각해 볼 수 있다.

일단 x좌표만을 생각해보자.

예제 입력의 x좌표만 직선상에 표현해 보면 다음과 같다.

 

 

11과  19를 잇는 간선은 길이가 8이지만,

11과 14를 잇는 간선은 3이고 14와 19를 잇는 간선은 길이가  5이다.

만약 11과 19를 잇는다면 두 개의 행성을 잇는데 8의 cost를 소모하지만

11과 14, 14와 19를 각각 잇는다면 같은 8의 cost로도 세 개의 행성을 연결할 수 있다.

 

즉, 최소 길이의 간선만 선택하는 MST 알고리즘(크루스칼)에 필요한 간선들의 정보는

행성들의 위치를 각 좌표계(x, y, z)에서 정렬했을 때 인접 행성으로의 간선만으로 충분하다.

그 이외의, 다른 행성과 연결하는 간선을 생성하더라도, 최선의 선택을 하는 크루스칼 알고리즘에서는 선택되지 않는다.

따라서 구현 알고리즘은 정렬의 시간 복잡도에 지배된다.

O(V logV)

 

단, 행성 u와 v를 x좌표에서 잇는 것보다 y나 z좌표에서 이어주는 것이 더 cost가 적게 드는 경우도 있을 수 있다.

따라서 x, y, z 좌표계에서 모두 인접 행성과 간선을 이어주고 

크루스칼 알고리즘을 진행 시, 생성된 모든 간선을 구별 없이 한 번에 정렬한 후 작은 간선부터 이어주면 된다.

 

 

코드