boj, 백준) 2887. 행성터널 ( C/C++)

1. 문제 링크

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

2887번: 행성 터널

 

2. 문제 개요

행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다.

두 행성을 x, y, z 좌표로 나타내고, 터널로 연결할 때 드는 비용은 min(|x2-x1|, |y2-y1|, |z2-z1|)로 정의한다.

터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하자.

 

3. 문제 힌트

모든 노드끼리 간선을 만들려고 하면 O(N^2) 즉 시간 초과가 된다.

간선을 모두 만들지 않고 MST를 만들 수 있는 방법은 없을까? -> 비용을 잘 보자.

 

4. 문제 풀이

이 문제의 특별한 점은 아마도 비용이 조금 특별하기 때문이라고 생각한다.

비용: min(|x2-x1|, |y2-y1|, |z2-z1|) 

그래서 저 3가지 경우 중 1개가 두 노드 중 적절한 비용으로 선택될 것이고 를 1개씩 1개씩 분리해서 살펴보자.

 

x축 기준:

3가지 경우중 첫 번째 경우 x2-x1이 비용이 되는 경우를 살펴보자.

각 노드(행성)를 x축 기준으로 정렬해보자.

0,1,2.... x-1, x 순으로 정렬될 것이고, 정렬된 두 번째 노드 기준으로 봤을 때, 비용의 후보가 될 수 있는 노드는 인접한 두 노드(첫 번째, 세 번째)뿐이다.

왜냐하면, x축으로 정렬했고 비용은 |x2-x1| 과 같이 x축 성분만 보기 때문이다. 그래서, 첫 번째 노드가 인접한 두 번째 노드가 아닌 세 번째 노드와 연결한다 한들 두 번째 노드보다 멀기 때문에 연산에서 제외될 것이다.

 

y, z축도 마찬가지로 해당 축으로 정렬 후 인접한 노드와 연결한다.

 

이렇게 보면 3(N-1) 개의 노드만 관찰하면 MST를 만들 수 있다.

 

문제를 풀면서 비용을 계속

x, y, z 정점의 차의 합으로 생각해서 어떻게 구하지..라고 계속 생각했다.

아마도 내 생각이지만, 비용 계산방식이 특이해서 이렇게 구할 수 있었다고 생각한다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

struct node {
	int x, y, z,idx;
	node() {}
	node(int x_, int y_, int z_, int idx_) : x(x_), y(y_), z(z_), idx(idx_) {}
};
struct edge {
	int u, v, c;
	edge() {}
	edge(int u_, int v_, int c_) : u(u_), v(v_), c(c_) {}

	/*bool operator < (edge &e){
		return this->c < e.c;
	}*/
	
};
struct disjointset {
	vector<int> root;

	void init(int size){
		root.resize(size);
		for (int i = 0; i < size; ++i)
			root[i] = i;
		return;
	}
	
	int find(int x) {
		if (root[x] == x)
			return x;
		return root[x] = find(root[x]);
	}

	bool merge(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (x != y) {
			root[y] = x;
			return true;
		}
		else
			return false;
	}

}dis;

bool compx(node &a, node &b) {
	return a.x < b.x;
}
bool compy(node &a, node &b) {
	return a.y < b.y;
}
bool compz(node &a, node &b) {
	return a.z < b.z;
}
bool compe(edge &a, edge &b) {
	return a.c < b.c;
}
int n;
vector<node> v;
vector<edge> ans;

int main() 
{
	scanf("%d", &n);
	dis.init(n);
	for (int i = 0; i < n; ++i)
	{
		node t;
		scanf("%d %d %d", &t.x, &t.y, &t.z);
		t.idx = i;
		v.push_back(t);
	}

	sort(v.begin(), v.end(), compx);
	for (int i = 0; i < n - 1; ++i){
		edge t;
		t.u = v[i].idx;
		t.v = v[i + 1].idx;
		t.c = v[i + 1].x - v[i].x;
		ans.push_back(t);
	}
	sort(v.begin(), v.end(), compy);
	for (int i = 0; i < n - 1; ++i) {
		edge t;
		t.u = v[i].idx;
		t.v = v[i + 1].idx;
		t.c = v[i + 1].y - v[i].y;
		ans.push_back(t);
	}
	sort(v.begin(), v.end(), compz);
	for (int i = 0; i < n - 1; ++i) {
		edge t;
		t.u = v[i].idx;
		t.v = v[i + 1].idx;
		t.c = v[i + 1].z - v[i].z;
		ans.push_back(t);
	}

	sort(ans.begin(), ans.end(), compe);

	int cnt = 0, ret = 0;
	for (int i = 0; i < ans.size(); ++i) {
		if (dis.merge(ans[i].u, ans[i].v)) {
			cnt++;
			ret += ans[i].c;
		}
		if (cnt == n - 1)
			break;
	}

	printf("%d", ret);
	return 0;
}

 

6. 결과 사진