백준 2887번 행성 터널

사용한 알고리즘: MST(최소 스패닝 트리)

​

핵심은 x, y, z축 별로 생각하는 것이였습니다.

각 행성들을 최소 비용으로 연결하여 하나의 컴포넌트를 만드는 것이 목적입니다.

이를 생각하여 x축을 생각해보면,

각 행성들의 x 좌표만을 정렬 해서, A1.x, A2.x, A3.x, ... 와 같이 정렬 됐다고 합시다.

이때 각 행성들은 바로 다음 행성과 연결 될 수 밖에 없습니다. ( 최소 비용을 구하는 것이기 때문)

예를 들어, A1.x 는 A2.x 와 연결 될 수 밖에 없습니다. 즉 A1.x 는 A3.x, A4.x, ... 들과 연결될 수 없습니다.

따라서 이를 생각하여 x, y, z 축 기준으로 각각 정렬하여,

각 이웃한 행성들을 연결하는 비용들을 구해서, 한데 모았습니다.

​

이후 이 x,y,z축 비용들을 한데 모아놓은 벡터를 정렬하여,

하나의 컴포넌트를 만드는 최소 비용을 구했습니다.

이때 A1, A2 행성이 연결해야하는지 확인하는데에, 같은 컴포넌트인지 union-find를 이용했습니다.

이후 N-1번 만큼 연결이 되면, N개의 행성들은 모두 연결됐으므로 연결하는 과정을 끝내고,

답을 도출했습니다.

​

	#include <bits/stdc++.h>
	using namespace std;
	#define pii pair<int, int>
	const int INF = 987654321;
	int uf[100000];
	int find(int a){
	if(uf[a]<0) return a;
	return uf[a] = find(uf[a]);
	}
	void merge(int a, int b){
	a = find(a);
	b = find(b);
	if(a==b) return;
	uf[b]=a;
	}
	struct star{
	int num;
	int x;
	int y;
	int z;
	star(): star(0,0,0,0){}
	star(int _num, int _x, int _y, int _z) : num(_num), x(_x), y(_y), z(_z){}
	};
	vector<star> S;
	bool cmpX(star &s1, star &s2){
	if(s1.x < s2.x) return true;
	return false;
	}
	bool cmpY(star &s1, star &s2){
	if(s1.y < s2.y) return true;
	return false;
	}
	bool cmpZ(star &s1, star &s2){
	if(s1.z < s2.z) return true;
	return false;
	}
	struct Di{
	int A;
	int B;
	int length;
	Di():Di(0,0,0){}
	Di(int _A, int _B, int _length) : A(_A), B(_B), length(_length){}
	bool operator<(const Di& rhs) const{
	if(length==rhs.length) return A < rhs.A;
	return length < rhs.length;
	}
	};
	int N;
	long long ans;
	vector<Di> arr;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	memset(uf,-1,sizeof(uf));
	cin >> N;
	for (int i = 0; i < N; ++i){
	int a, b, c;
	cin >> a >> b >> c;
	S.push_back(star(i,a,b,c));
	}
	sort(S.begin(),S.end(),cmpX);
	for (int i = 0; i < N-1; ++i)
	arr.push_back(Di(S[i].num,S[i+1].num,S[i+1].x-S[i].x));
	sort(S.begin(),S.end(),cmpY);
	for (int i = 0; i < N-1; ++i)
	arr.push_back(Di(S[i].num,S[i+1].num,S[i+1].y-S[i].y));
	sort(S.begin(),S.end(),cmpZ);
	for (int i = 0; i < N-1; ++i)
	arr.push_back(Di(S[i].num,S[i+1].num,S[i+1].z-S[i].z));
	sort(arr.begin(),arr.end());
	int cnt = 0;
	for (int i = 0; i < arr.size(); ++i){
	int star1 = arr[i].A;
	int star2 = arr[i].B;
	if(find(star1)!=find(star2)){
	cnt++;
	merge(star1,star2);
	ans += arr[i].length;
	}
	if(cnt==N-1) break;
	}
	cout << ans << '\n';
	return 0;
	}

view raw BOJ 2887.cpp hosted with ❤ by GitHub