[백준 BOJ/C++] 1774 우주신과의 교감

 

1774번: 우주신과의 교감

크루스칼 알고리즘을 연습해보기 좋은 문제다.
특별히 복잡하게 꼬아놓은 부분은 없는데 사전에 일부 간선만 주어지고 나머지 가능한 모든 간선을 추가하는 과정만 추가되었다.

 

 

입력으로 주어지는 모든 노드들 사이에 가능한 모든 간선들을 list up 하고 각 간선의 길이를 계산해두고 이를 토대로 크루스칼 알고리즘을 이용해 최소 신장 트리를 찾아주면 된다.
단, 입력으로 주어지는 이미 연결된 통로는 최소 신장 트리에 반드시 포함되어야 하며 새로 추가한 간선들의 길이의 합을 출력해야 한다.

 

 

---

 

문제의 포인트

1. 최소 신장 트리를 구할 수 있는가?
2. 간선의 길이는 주어지지 않는다.

 

 

최소 신장 트리

사이클 없이 모든 노드를 연결하는 최소 신장 트리 (MST, Minimum Spanning Tree)만 만들 수 있다면 해결 가능한 문제다.
가장 대표적인 Kruskal Algoritm을 사용해서 구해주면 된다.
이 문제에서는 간선 정보가 일부만 주어지기 때문에 아래와 같은 순서로 접근했다.

 

 

1. 입력으로 주어지는 간선을 트리에 포함시킨다.
2. 모든 노드 사이에 간선을 만들고 거리를 계산해서 vector에 넣어준다.
3. 간선 vector를 오름차순으로 정렬한다.
4. 정렬되어있는 간선 vector에서 순서대로 간선을 선택하고 거리를 누적한다.

 

 

사실 위 과정은 Kruskal algoritm 그 자체다.
노드정보는 입력한 순서대로 번호를 붙였다고 생각하고 vector의 index와 sync해서 사용하면 된다.
간선 정보는 시작과 끝 노드 번호의 쌍으로 표현하되 방향은 없다.
간선은 vector를 이용하되 {거리, {시작점, 끝점}} 형태로 pair를 중첩하여 표현해봤다.

 

일반적인 크루스칼 알고리즘에서와 마찬가지로 간선을 트리에 포함했음을 나타내는 방법은 cycle table(parent table) 을 이용했다.
자기 자신의 노드 번호로 초기화된 배열을 이용해, 선택할 때마다 연결된 최상위 parent의 노드 번호를 넣어줌으로써 최소신장 트리에 포함된 간선인지 간단히 확인할 수 있다.
오름차순으로 정렬한 뒤 간선 vector에서 순서대로 가져오기만 하면 최소 비용으로 트리를 만들 수 있다.

 

 

거리 계산

유클리드 호제법이니 피타고라스의 정리니 이름은 가물가물 하더라도 대각선 길이를 구하는 방법 하면 무조건 반사처럼 떠오르는 그대로

"대각선 길이의 제곱 = 가로 길이의 제곱 + 세로 길이의 제곱" 을 이용하면 된다.
따라서 sqrt를 사용해야 하고 소숫점으로 표현된다.

 

 

---

 

 

전체 Code

 

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

using namespace std;

int N, M;

vector<pair<int, int>> node;
vector<pair<double, pair<int, int>>> edge;
int parent[1000 + 10];

double get_distance(int x1, int y1, int x2, int y2) {
	return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int get_parent(int n) {
	if (parent[n] == n)
		return n;
	return get_parent(parent[n]);
}

void union_parent(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);

	if (a < b)
		parent[b] = a;
	else
		parent[a] = b;
}

bool find_parent(int a, int b) {
	a = get_parent(a);
	b = get_parent(b);

	if (a == b)
		return true;
	else
		return false;
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, j, x, y, a, b;
	double res = 0.0;

	cin >> N >> M;

	for (i = 0; i < N; i++) {
		cin >> x >> y;
		node.push_back({ x, y });
		parent[i + 1] = i + 1;
	}

	for (i = 0; i < M; i++) {
		cin >> x >> y;
		union_parent(x, y);
	}

	for (i = 0; i < N; i++) {
		for (j = i + 1; j < N; j++) {
			edge.push_back({get_distance(node[i].first, node[i].second, node[j].first, node[j].second), { i + 1, j + 1 } });
		}
	}

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

	for (i = 0; i < edge.size(); i++) {
		a = edge[i].second.first;
		b = edge[i].second.second;
		if (!find_parent(a, b)) {
			union_parent(a, b);
			res += edge[i].first;
		}
	}
	cout << fixed;
	cout.precision(2);
	cout << res << "\n";
}