문제
때는 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보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다.
출력
첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.
예제 입력
5 11 -15 -15 14 -5 -15 -1 -1 -5 10 -4 -1 19 -4 19
예제 출력
4
문제 풀이
최소 스패닝 트리 (MST) 로 풀면 된다.
그래프 구성만 하고 MST 알고리즘 돌리면 된다.
답안 코드
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX_V 100000
int V;
vector<pair<long long, pair<int,int>>> edges;
pair<int,int> x[MAX_V], y[MAX_V], z[MAX_V];
int unionGroup[MAX_V];
int find(int i){
while(unionGroup[i] != i) i = unionGroup[i] = unionGroup[unionGroup[i]];
return i;
}
void unionSet(int u, int v){
unionGroup[find(u)] = find(v);
}
bool isUnion(int u, int v){
return find(u) == find(v);
}
int main(){
scanf("%d", &V);
for(int i = 0; i < V; ++i){
scanf("%d %d %d", &x[i].first, &y[i].first, &z[i].first);
x[i].second = y[i].second = z[i].second = i;
}
sort(x, x+V);
sort(y, y+V);
sort(z, z+V);
for(int i = 1; i < V; ++i){
edges.push_back(make_pair(x[i].first-x[i-1].first, make_pair(x[i].second, x[i-1].second)));
edges.push_back(make_pair(y[i].first-y[i-1].first, make_pair(y[i].second, y[i-1].second)));
edges.push_back(make_pair(z[i].first-z[i-1].first, make_pair(z[i].second, z[i-1].second)));
}
long long mst_cost = 0;
sort(edges.begin(),edges.end());
for(int i = 0; i < V; ++i)
unionGroup[i] = i;
for(int i = 0; i < edges.size(); ++i){
auto e = edges[i].second;
if(!isUnion(e.first, e.second)){
mst_cost += edges[i].first;
unionSet(e.first, e.second);
}
}
printf("%lld\n", mst_cost);
return 0;
}
Leave A Comment