[백준 1774] 우주신과의 교감 (C++)

문제 링크: https://www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

1. 주의할 점

- MST 알고리즘에 대해 알고 있어야 한다

- 이미 연결되어 있는 경우, 어떻게 처리할 것인지 고민한다

 

2. 구현

- 크루스칼 알고리즘을 통해 MST를 해결한다

- 모든 우주신들의 좌표를 X[], Y[] 배열에 저장한다

- 이미 연결된 통로의 정보를 입력받아 Make_union(a,b) 함수를 통해 A와 B의 부모를 일치시킨다

- 서로 다른 신과 그 사이의 거리를 Cal(a,b) 함수를 통해 계산하여 우선순위 큐에 삽입한다

- 우선순위 큐에서 1개씩 빼면서 시작점과 끝점의 부모가 다른 경우, 부모를 통일시키고 해당 간선의 길이를 Result에 더한다

- 출력은 소수 2자리까지 출력한다

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
struct info {
	int s, e;
	double val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};
info tmp;

double x[1001], y[1001];
int node, edge;
int par[1001];
double result = 0;

double cal(int a, int b) {
	double dx = fabs(x[a] - x[b]);
	double dy = fabs(y[a] - y[b]);
	double dist = hypot(dx, dy);
	return dist;
}

int find_parent(int x) {
	if (par[x] == x) return x;
	return par[x] = find_parent(par[x]);
}

void make_union(int a, int b) {
	a = find_parent(a);
	b = find_parent(b);
	if (a > b) par[a] = b;
	else if (a < b) par[b] = a;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int a, b;
	priority_queue<info, vector<info>, cmp> pq;
	cin >> node >> edge;
	for (int i = 1; i <= node; i++)
		par[i] = i;
	for (int i = 1; i <= node; i++) 
		cin >> x[i] >> y[i];	
	for (int i = 0; i < edge; i++) {
		cin >> a >> b;
		make_union(a, b);
	}
	for (int i = 1; i < node; i++) {
		for (int j = i + 1; j <= node; j++) {
			tmp.s = i;
			tmp.e = j;
			tmp.val = cal(i, j);
			pq.push(tmp);
		}
	}
	while (!pq.empty()) {
		int s = pq.top().s;
		int e = pq.top().e;
		double d = pq.top().val;
		pq.pop();
		int ps = find_parent(s);
		int pe = find_parent(e);
		if (ps == pe) continue;
		make_union(s, e);
		result += d;
	}
	cout << fixed;
	cout.precision(2);
	cout <<result;
	system("pause");
	return 0;
}