C++ / 백준 / 2887 / 행성 터널

문제

 

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

2887번: 행성 터널

문제풀이

 

최근에 swea에서 풀어본 문제랑 비슷해 보여서 도전해 봤다.

크루스칼 알고리즘을 이용해 풀었다.

메모리 초과가 발생해서 질문글을 보니 행성의 개수가 최대 100,000개라  N^2의 간선이 아닌 3*N의 간선으로 풀어야 한다고 했다. 해당 질문글을 참고하여 간선을 구하는 방법을 바꿨다.

 

터널을 연결할 때 드는 비용은 두 행성 간의 x의 차, y의 차, z의 차 중 최솟값이 비용이 된다.

따라서 x, y, z별로 좌표를 정리하여 N-1만큼의 간선들을 구하고 크루스칼 알고리즘을 사용하여 풀면 된다.

코드가 길어 보이지만 반복하는 게 있어서 길뿐이다..

 

구조체를 두 개 선언했다.

Coord 구조체는 해당 idx를 의미하는 num, 그리고 각 좌표 x, y, z.

Link 구조체는 행성 1, 행성 2, 행성 1과 행성 2를 연결하는 비용인 cost.

좌표를 저장하기 위한 벡터 vector <Coord> planet.

간선들을 저장하는 벡터 vector <Link> tunnel.

union_find를 하기 위한 vector <int> parent를 선언했다.

 

	sort(planet.begin(), planet.end(), compareX);

	for (int idx = 0; idx + 1 < N; ++idx) {		
		Link link;
		link.node1 = planet[idx].num;
		link.node2 = planet[idx + 1].num;
		link.cost = abs(planet[idx].x - planet[idx + 1].x);
		tunnel.push_back(link);
	}

compareX는 x를 오름차순으로 정렬하기 위한 compare함수이다.

x를 오름차순으로 정렬한 뒤, idx의 x와 idx+1의 x의 차를 구해 cost에 저장하고 간선 벡터에 저장한다.

y, z도 위와 마찬가지로 간선을 구한다.

 

 

	sort(tunnel.begin(), tunnel.end(), cmp);

	int cnt(0), answer(0);

	for (int idx = 0; idx < tunnel.size(); ++idx) {
		int node1 = tunnel[idx].node1;
		int node2 = tunnel[idx].node2;		
		if (isUnion(node1, node2) == true) {			
			continue;
		}
		else {			
			merge(node1, node2);
			answer += tunnel[idx].cost;
			++cnt;
			if (cnt == N - 1) break;
		}
	}
	cout << answer;

간선을 다 구했으면 연결 비용을 오름차순으로 정렬한다.

그리고 저장된 간선을 하나하나씩 꺼내어 해당 간선을 사용하면 사이클이 발생하는지를 판별한다.

발생한다면 넘어간다.

발생하지 않는다면 간선을 사용할 것이므로 merge를 통해 부모값을 같게 한 뒤, 해당 비용을 answer에 더하고 간선 개수를 1 더한다.

만약 간선을 N-1개만큼 골랐다면 완성이므로 break를 통해 반복문을 종료하고 answer을 출력한다.

 

 

코드

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Coord {
	int num;
	int x;
	int y;
	int z;
};

struct Link {
	int node1;
	int node2;
	int cost;
};

vector<int>parent;
vector<Link> tunnel;
vector<Coord>planet;

bool cmp(Link& l1, Link&l2) {
	return l1.cost < l2.cost;
}

bool compareX(Coord& c1, Coord& c2) {
	return c1.x < c2.x;
}

bool compareY(Coord& c1, Coord& c2) {
	return c1.y < c2.y;
}

bool compareZ(Coord& c1, Coord& c2) {
	return c1.z < c2.z;
}

int union_find(int node) {
	if (parent[node] == node) return node;
	else return parent[node]= union_find(parent[node]);
}

void merge(int node1, int node2) {
	node1 = parent[node1];
	node2 = parent[node2];

	if (node1 > node2) swap(node1, node2);
	parent[node2] = node1;
}

bool isUnion(int node1, int node2) {
	if (union_find(node1) == union_find(node2)) {		
		return true;
	}
	else return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0);
	cin >> N;	

	planet = vector<Coord>(N);
	parent = vector<int>(N, 0);

	for (int idx = 0; idx < N; ++idx) {
		cin >> planet[idx].x >> planet[idx].y >> planet[idx].z;
		planet[idx].num = idx;
		parent[idx] = idx;
	}	

	sort(planet.begin(), planet.end(), compareX);

	for (int idx = 0; idx + 1 < N; ++idx) {		
		Link link;
		link.node1 = planet[idx].num;
		link.node2 = planet[idx + 1].num;
		link.cost = abs(planet[idx].x - planet[idx + 1].x);
		tunnel.push_back(link);
	}

	sort(planet.begin(), planet.end(), compareY);

	for (int idx = 0; idx + 1 < N; ++idx) {
		Link link;
		link.node1 = planet[idx].num;
		link.node2 = planet[idx + 1].num;
		link.cost = abs(planet[idx].y - planet[idx + 1].y);
		tunnel.push_back(link);
	}

	sort(planet.begin(), planet.end(), compareZ);

	for (int idx = 0; idx + 1 < N; ++idx) {
		Link link;
		link.node1 = planet[idx].num;
		link.node2 = planet[idx + 1].num;
		link.cost = abs(planet[idx].z - planet[idx + 1].z);
		tunnel.push_back(link);
	}
	
	sort(tunnel.begin(), tunnel.end(), cmp);

	int cnt(0), answer(0);

	for (int idx = 0; idx < tunnel.size(); ++idx) {
		int node1 = tunnel[idx].node1;
		int node2 = tunnel[idx].node2;		
		if (isUnion(node1, node2) == true) {			
			continue;
		}
		else {			
			merge(node1, node2);
			answer += tunnel[idx].cost;
			++cnt;
			if (cnt == N - 1) break;
		}
	}
	cout << answer;
}