[백준 4386] 별자리 만들기 (C++)

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

4386번: 별자리 만들기

1. 주의할 점

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

- Float값으로 받아들인 후, 소수점 이하 2번째 자리까지 반올림 한 값을 지니고 있어야 한다

 

2. 구현

- 크루스칼 알고리즘을 통하여 구현한다

- 모든 정점에 대해 X,Y 값을 입력 받은 후 모든 정점들을 비교하며 계산한 거리, 비교한 두 Node를 우선순위큐에 넣는다

- 값의 오름차순순으로 정렬된 우선순위 큐에서 원소를 1개씩 빼면서 만약 같은 집합이라면(Find_par()의 값이 같다면) Continue, 같지 않다면 같은 집합으로 만든다(Make_union()함수를 통해) + 가중치의 값을 Result에 더한다

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
int par[101];

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

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

struct info {
	int start, end;
	float val;
};

struct cmp {
	bool operator()(info &a, info &b) {
		return a.val > b.val;
	}
};

info tmp;
float a[101], b[101];
int main() {
	int num;
	cin >> num;
	for (int i = 1; i <= num; i++)
		par[i] = i;
	priority_queue<info, vector<info>, cmp> pq;
	for (int i = 1; i <= num; i++) {
		cin >> a[i] >> b[i];
	}
	for (int i = 1; i < num; i++) {
		for (int j = i + 1; j <= num; j++) {
			float val = (a[i] - a[j])*(a[i] - a[j]) + (b[i] - b[j])*(b[i] - b[j]);
			val = sqrt(val);
			val = roundf(val * 100) / 100;
			tmp.start = i;
			tmp.end = j;
			tmp.val = val;
			pq.push(tmp);
		}
	}
	float result = 0;
	while (!pq.empty()) {
		int s = pq.top().start;
		int e = pq.top().end;
		float v = pq.top().val;
		pq.pop();
		if (find_par(s) == find_par(e)) continue;		//이미 연결된 경우
		else {
			make_union(s, e);
			result += v;
		}
	}
	cout << result;
	system("pause");
	return 0;
}