[백준] 2887번 - 행성 터널

백준 2887번 행성 터널

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

---

코드

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct pt{
	int num;
	int x,y,z;
};
struct edge{
	int f,t,w;
};

vector<pt> node;
vector<edge> v;
int p[100003];

bool x(pt a, pt b){	return a.x < b.x;}
bool y(pt a, pt b){	return a.y < b.y;}
bool z(pt a, pt b){	return a.z < b.z;}
bool cmp(edge a, edge b){	return a.w < b.w;}

int find(int u){
	if(p[u] == u)	return u;
	return p[u] = find(p[u]);
}

void v_push(int u){
	int dist;
	for(int i=0;i<node.size()-1;i++){
		int a = node[i].num;
		int b = node[i+1].num;
		if(u==0)	dist=abs(node[i].x - node[i+1].x);
		if(u==1)	dist=abs(node[i].y - node[i+1].y);
		if(u==2)	dist=abs(node[i].z - node[i+1].z);
		v.push_back((edge){a, b, dist});
	}
}

int kruskal(){
	sort(v.begin(), v.end(), cmp);
	int sum = 0;
	for(int i=0;i<v.size();i++){
		int a = find(v[i].f);
		int b = find(v[i].t);
		if(a==b)	continue;
		p[a] = b;
		sum += v[i].w;
	}
	return sum;
}

int main(){
	int n;
	cin >> n;
	for(int i=0;i<n;i++)	p[i] = i;
	for(int i=0;i<n;i++){
		int a,b,c;
		cin >> a >> b >> c;
		node.push_back((pt){i,a,b,c});
	}
	
	sort(node.begin(), node.end(), x), v_push(0);
	sort(node.begin(), node.end(), y), v_push(1);
	sort(node.begin(), node.end(), z), v_push(2);
	
	cout << kruskal();
}

---

풀이

1. 입력받은 행성을 node 벡터에 저장

2. 각 노드들을 연결한 간선을 저장하는 v 벡터 생성
   - 모든 노드를 연결하게 되면 O(n^2)
   - 따라서 x, y, z 별로 정렬하고 i번째 노드와 i+1번째 노드를 연결
   - v 벡터를 w를 기준으로 오름차순 정렬

   

3. 크루스칼