※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.
3차원 좌표가 주어져 있고, 두 행성간 터널을 연결할 때 드는 비용은 x,y,z 좌표 중 차이가 최소가 되는 경우라고 하였으므로, 모든 행성간의 x,y,z에 대해 한 번씩 정렬한 후, 정렬된 행성을 $i$번째와 $i-1$번째 행성과 연결하여 후보군에 집어 넣습니다.
이렇게 각 좌표에 대해 최솟값 연결 후보군을 집어 넣은 다음, 최소 스패닝 알고리즘을 이용하여 모든 행성에 대해 연결시켜주면 됩니다. 소스코드에서는 크루스칼 알고리즘을 사용하였습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
class Node
{
public:
int no, x, y, z;
Node() {}
Node(int no, int x, int y, int z) : no(no), x(x), y(y), z(z) {}
};
class Edge
{
public:
int src, dest, cost;
Edge() {}
Edge(int a, int b, int c) : src(a), dest(b), cost(c) {}
bool operator <(const Edge &n)
{
return cost < n.cost;
}
};
bool cmp(Node a, Node b)
{
return a.x < b.x;
}
bool cmp2(Node a, Node b)
{
return a.y < b.y;
}
bool cmp3(Node a, Node b)
{
return a.z < b.z;
}
int par[100001];
int find(int x)
{
if (x == par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y)
{
par[find(y)] = find(x);
}
int main()
{
ios::sync_with_stdio(false);
int n;
long long ans=0;
vector<Node> vn;
vector<Edge> chk;
cin >> n;
for (int i = 0; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
vn.push_back({ i+1,a,b,c });
}
sort(vn.begin(), vn.end(), cmp);
for (int i = 1; i < n; i++)
chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].x - vn[i - 1].x) });
sort(vn.begin(), vn.end(), cmp2);
for (int i = 1; i < n; i++)
chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].y - vn[i - 1].y) });
sort(vn.begin(), vn.end(), cmp3);
for (int i = 1; i < n; i++)
chk.push_back({ vn[i].no,vn[i-1].no,abs(vn[i].z - vn[i - 1].z) });
for (int i = 1; i <= n; i++) par[i] = i;
sort(chk.begin(), chk.end());
for (int i = 0; i < chk.size(); i++)
{
int l = find(chk[i].src), r = find(chk[i].dest);
if (l != r)
{
merge(l, r);
ans += chk[i].cost;
}
}
cout << ans;
}