👓 문제 설명
때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.
행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.
민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.
💣 제한 사항
- 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다.
- 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
- 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
🚨 접근 방법
최소 비용 신장 트리 (MST)의 문제이다.
정점의 개수가 10만개 주어진다.
x,y,z로 총 3종류가 있다.
따라서, 간선의 총 개수는 3 x (50000 x 100000) = 약 150억이다.
이를 전부 구하게 되면 메모리 및 시간 초과가 발생할 것이다.
따라서, 문제에서 요구하는 N-1개의 간선을 효율적으로 구해야한다.
어떻게 구할 수 있을까?
|x1-x2|, |y1-y2|, |z1-z2|가 의미 하는 것이 뭘까 생각해보자.
두 좌표 사이의 거리이다.
두 좌표 사이의 거리가 작은 것은 어떻게 구할까?
오름 또는 내림 차순으로 정렬하여 인접한 두 값이 거리가 가까운 뜻 아닌가?
따라서, x, y, z를 모두 정렬한 후 인접한 두 인덱스 값에 해당하는 좌표의 차이를 간선의 후보군으로 저장하면 된다.
🚈 풀이
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
int n;
int parent[100001];
// x,y,z에 대해 (좌표, 번호를 저장)
vector<pair<int, int>>pos[3];
// 간선 저장
struct info {
int dis, s, e;
};
bool cmp(info a, info b) {
return a.dis < b.dis;
}
vector<info>edges;
void input() {
for (int i = 0; i < n; i++) {
parent[i] = i;
int x, y, z;
cin >> x >> y >> z;
pos[0].push_back({ x,i });
pos[1].push_back({ y,i });
pos[2].push_back({ z,i });
}
// x,y,z의 좌표를 정렬
sort(pos[0].begin(), pos[0].end());
sort(pos[1].begin(), pos[1].end());
sort(pos[2].begin(), pos[2].end());
for (int i = 0; i < n-1; i++) {
int dis_x = abs(pos[0][i].first - pos[0][i + 1].first);
int dis_y = abs(pos[1][i].first - pos[1][i + 1].first);
int dis_z = abs(pos[2][i].first - pos[2][i + 1].first);
edges.push_back({ dis_x,pos[0][i].second,pos[0][i + 1].second });
edges.push_back({ dis_y,pos[1][i].second,pos[1][i + 1].second });
edges.push_back({ dis_z,pos[2][i].second,pos[2][i + 1].second });
}
sort(edges.begin(), edges.end(), cmp);
}
int find(int tar) {
if (tar == parent[tar])return tar;
int ret = find(parent[tar]);
parent[tar] = ret;
return ret;
}
void setUnion(int a, int b) {
int t1 = find(a);
int t2 = find(b);
if (t1 == t2)return;
parent[t2] = t1;
}
void Kruskal() {
int selectCount = 0;
long long int result = 0;
for (auto p : edges) {
int start = p.s;
int end = p.e;
int dis = p.dis;
// 사이클 검사
if (find(start) == find(end))continue;
setUnion(start, end);
result += dis;
selectCount++;
if (selectCount == n - 1)break;
}
cout << result;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
input();
Kruskal();
return 0;
}