c++ 백준_4386_"별자리 만들기"

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

4386번: 별자리 만들기

Kruskal 알고리즘을 사용하였다.

​

n개의 노드들을 최단 비용으로 이어버리면 된다.

각 노드에서 각 노드를 향하는 거리를 계산하여

우선수위큐에 넣어 주어 진행하였다.

#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;

int n;
pair<double, double> coord[100];
int parent[100];

typedef struct {
	int u, v;
	double cost;
}node;


struct comp {
	bool operator()(node a, node b) {
		return a.cost > b.cost;
	}
};

void init_parent() {
	for (int i = 0; i < n; i++) {
		parent[i] = i;
	}
}

int FIND(int x) {
	if (parent[x] == x)
		return parent[x];
	return parent[x] = FIND(parent[x]);
}

void UNION(int x, int y) {
	x = FIND(x);
	y = FIND(y);
	if (x > y)
		parent[x] = y;
	else
		parent[y] = x;
}

double kruskal(priority_queue<node, vector<node>, comp> pq ) {

	init_parent();

	int edge = 0;

	double result = 0;

	while (edge < n - 1) {
		node e = pq.top();
		pq.pop();

		int u = FIND(e.u);
		int v = FIND(e.v);
		
		if (u != v) {
			UNION(u, v);
			edge++;
			result += e.cost;
		}
	}

	return result;
}



int main(void) {

	cin >> n;

	priority_queue<node, vector<node>, comp> pq;
	
	for (int i = 0; i < n; i++) {
		cin >> coord[i].first >> coord[i].second;
	}

	for (int i = 0; i < n; i++) {
		pair<double, double> a = coord[i];
		for(int j = i + 1; j < n; j++) {
			pair<double, double> b =  coord[j];

			double dist = sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
			pq.push({ i,j,dist });
			
		}
	}


	cout << fixed;
	cout.precision(2);
	cout << kruskal(pq);

}