백준 2887 : 행성 터널

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

행성터널. 최소스패닝트리 문제이다.

간선의 정보를 주는 것이 아니라 정점의 정보(x, y, z 좌표) 를 준다.

따라서 주어진 정점의 정보를 토대로 후보 간선들을 정해야 하는데

정점 N이 100,000 이므로 N^2 연산으로 모든 행성들을 일일이 다 연결시키면

초과가 발생한다.

따라서 간선의 후보를 주어진 조건에 맞게 적절히 설정해야한다.

우선 행성과 행성간의 3차원상에서의 거리가 가중치가 아닌

x,y,z좌표 중에서 거리가 짧은것 하나만 가중치가 된다.

또한, 모든 행성을 후보로 연결할 필요 없이 x,y,z 좌표중 행성 가까이에 있는 행성들만 후보터널로 사용하면된다.

예시가 다음과 같이 주어졌다

행성번호	1	2	3	4	5
x , y, z	11, -15, -15	14, -5, -15	-1, -1, -5	10, -4, -1	19, -4, 19

1. 우선 x 크기를 기준으로 행성들을 sort 한다.

행성번호	3	4	1	2	5
x	-1	10	11	14	19

이렇게 정렬했을경우 행성 3-4, 4-1, 1-2, 2-5 만 연결하는 터널을 후보로 넣으면 된다.

이때 터널의 정보는 3,4를 연결했다는 것과 가중치인 11(|-1-10|)을 가지고 있다.

만약 3-2를 연결할 경우 가중치가 |-1-14| = 15 가 되는데 3과 연결되는 다리 중 이미 가중치 11인 최소의 다리가 존재하기때문에

어짜피 최소 비용을 갖는 다리의 후보가 될 수 없다.

마찬가지로 y, z 기준으로 행성들을 sort하고 터널정보를 집어넣는다.

최종적으로 터널들을 가중치기준 오름차순으로 정렬한 다음 kruskal 알고리즘을 적용시킨다.

* 이렇게 했을 경우 터널정보에 중복된 행성이 들어있을 수 있다. x 기준으로 정렬시켰을때 생성된 터널 후보와 y 또는 z 기준으로

정렬시켰을때 터널후보가 같을 수 있기때문이다.

* 그렇다 하더라도 더 작은 가중치를 가진 터널후보(예 : x기준 가중치 11)가 이미 연결되었기 때문에 이후에 나오는

터널후보(y, z 기준 가중치 13, 15)는 등장하더라도 합병되지 못하고 무시된다. 따라서 행성의 연결은 min(|xA-xB|, |yA-yB|, |zA-zB|)

조건에 맞게 구현될 수 있다.

사실 이문제를 혼자서 완전히 풀지는 못했고 다른 분들의 아이디어를 참고했다.

참고했음에도 원리를 완벽히 이해하고 풀기까지 시간이 꽤 걸렸다 ㅠ

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #include <vector> #include <cmath> #include <algorithm> #define MAX 100001 using namespace std; int n, cost = 0; struct Planet{ int idx, x, y, z; }; bool cmpx (Planet a, Planet b){ return a.x < b.x; } bool cmpy (Planet a, Planet b){ return a.y < b.y; } bool cmpz (Planet a, Planet b){ return a.z < b.z; } struct Tunnel{ int i, j, w; bool operator < (const Tunnel &t) const { return w < t.w; } }; Planet planet[MAX]; vector<Tunnel> tunnel; int vRoot[MAX]; int findRoot(int v){ if(vRoot[v] == v) return v; return vRoot[v] = findRoot(vRoot[v]); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> planet[i].x >> planet[i].y >> planet[i].z; planet[i].idx = i; vRoot[i] = i; } sort(planet+1, planet+n+1, cmpx); for(int i = 1; i <= n-1; i++){ tunnel.push_back({planet[i].idx, planet[i+1].idx, abs(planet[i].x-planet[i+1].x)}); } sort(planet+1, planet+n+1, cmpy); for(int i = 1; i <= n-1; i++){ tunnel.push_back({planet[i].idx, planet[i+1].idx, abs(planet[i].y-planet[i+1].y)}); } sort(planet+1, planet+n+1, cmpz); for(int i = 1; i <= n-1; i++){ tunnel.push_back({planet[i].idx, planet[i+1].idx, abs(planet[i].z-planet[i+1].z)}); } sort(tunnel.begin(), tunnel.end()); for(Tunnel t : tunnel){ int rootI = findRoot(t.i); int rootJ = findRoot(t.j); if(rootI != rootJ){ vRoot[rootJ] = rootI; cost += t.w; } } cout << cost << '\n'; return 0; }