백준 No.2887 [행성 터널]

Baekjoon Online Judge No.2887 [행성 터널]

---

  문제 

2887번: 행성 터널 (acmicpc.net)

2887번: 행성 터널

---

  설명 

  최소 스패닝 트리(최소 스패닝 트리 / 최소 신장 트리 (MST)) 를 통해 풀 수 있는 문제이다. 각 정점끼리의 간선의 가중치의 값은 두 정점의 거리에 따른다. 결국 모든 정점 사이에 간선이 존재하게 된다. 정점의 수는 최대 100,000 개 이기 떄문에 이 때 총 간선의 수는 약 (100,000^2) / 2 개 이다. 총 대략 50억개의 간선이 있으므로, 이 간선들을 모두 구현하는 것은 정말 효율적이지도 못하고 AC도 못 받을 것 이다.

 

  크루스칼 알고리즘은 현재 간선들 중 최소 가중치의 값을 가지는 간선을 통해 하나의 최소 스패닝 트리가 생길 때 까지 어느 트리에 추가시킨다. 그리고 그 트리들이 합쳐지면서 최종적으로 하나의 최소 스패닝 트리가 생기는 것 이다.

 

  두 정점 a 와 b 사이의 간선의 가중치의 값은 min(|a.x - b.x|, |a.y - b.y|, |a.z - b.z|) 이다. 그러면 임의의 두 정점은 x, y, z 좌표중 하나에 의해 가중치의 값이 결정이 될 것이다. 크루스칼 알고리즘의 특징에 의해 어떠한 정점이 스패닝 트리에 포함이 될 땐 x, y, z 중 한 좌표를 이용한 가중치의 값들 중 가장 작은 값의 가중치를 가지는 간선을 추가하는 것이 좋을 것 이다. 모든 정점들이 연결이 되는 간선을 모두 정의하는 것이 아닌 가장 최소의 가중치 값을 가질 수 있는 간선을 추가하는 것 이다. 좌표에 아래와 같은 점들이 있다고 하자.

 이 정점들을 x, y, z 를 기준으로 오름차순으로 정렬들을 해 보았다. 그럼 아래와 같은 결과가 된다.

  점 A가 x좌표를 따졌을 때 가장 가까운 점은 바로 양 옆에 정의가 된 점 C 와 점 E 이다. 점 A 와 점 E 를 연결한 간선의 가중치는 x 좌표만 생각을 했을 때 0이다. 하지만 점 E 보다 우측에 정렬되어있는 정점들과 연결을 해 본다면 전부 A--E 간선의 가중치보다 같거나 큰 값을 가지게 된다. 

  y, z 좌표만을 따졌을 때 또한 임의의 정점은 바로 옆에 정의가 된 정점과 연결이 되어야 해당 좌표에서 가장 최소의 가중치 값을 가질 수 있다.

  즉, 위 정렬된 세 좌표에 대한 배열에 대해서 arr[k] 정점은 arr[k + 1] ... (k = 1 ~ n - 1) 정점과 같이 하나의 간선을 이루게 된다. 이러한 규칙을 가지고 생성되는 간선들을 전부 활용한다. 세 좌표에 대해서 모두 O(N) 의 시간복잡도를 가질 수 있는 선형탐색을 통해 해당되는 간선을 배열에 추가한다. 이렇게 한다면, 100,000 개의 정점이 있는 경우엔 약 300,000 개의 간선만 발생하게 된다. 그 후 이 간선들을 가중치 값을 기준으로 오름차순 정렬을 한 후 크루스칼 알고리즘을 통해 최소 스패닝 트리를 구현할 수 있다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;
typedef long long ll;

struct Node {
	int idx;
	int x, y, z;
};

struct Edge {
	int a, b;
	ll val;

	bool operator < (Edge a) {
		return val < a.val;
	}
};

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;
}

vector<bool> visit;
vector<Node> node;
vector<Edge> List;
vector<int> parent;
int n;
ll answer = 0;

int find(int a) {
	if (parent[a] == a) return a;
	else return parent[a] = find(parent[a]);
}

void Union(int a, int b) {
	int pa = find(a);
	int pb = find(b);

	parent[pb] = parent[pa];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n;
	node.resize(n);
	visit.assign(n, false);
	parent.assign(n, 0);

	for (int i = 0; i < n; i++) {
		node[i].idx = i;
		cin >> node[i].x >> node[i].y >> node[i].z;
		parent[i] = i;
	}

	sort(node.begin(), node.end(), compX);
	for (int i = 0; i < n - 1; i++)
		List.push_back({ node[i].idx, node[i + 1].idx, abs(node[i + 1].x - node[i].x) });

	sort(node.begin(), node.end(), compY);
	for (int i = 0; i < n - 1; i++)
		List.push_back({ node[i].idx, node[i + 1].idx, abs(node[i + 1].y - node[i].y) });

	sort(node.begin(), node.end(), compZ);
	for (int i = 0; i < n - 1; i++)
		List.push_back({ node[i].idx, node[i + 1].idx, abs(node[i + 1].z - node[i].z) });

	sort(List.begin(), List.end());

	int A, B;

	for (int i = 0; i < List.size(); i++) {
		A = List[i].a;
		B = List[i].b;

		if (find(A) != find(B)) {
			answer += List[i].val;
			Union(A, B);
		}
	}

	cout << answer;
}