4386 별자리 만들기

4386번: 별자리 만들기

전형적인 Minimum Spanning Tree 문제이다.

입력으로 별의 x, y 좌표를 받아서 Complete Graph가 되도록 모든 별들 사이의 간선을 만들어준다.

그리고 이제부턴 크루스칼 알고리즘을 적용해서 간선을 정렬해서 최소 비용의 간선부터

루프를 생성하지 않으면 선택하는 식으로 풀면 된다.

 

간단한 문제였는데, 오랜만에 풀다 보니 사소한 데서 에러가 좀 있었다. 그리고 코드도 좀 더럽게 짠 거 같기도 하고...

꾸준히 풀어야 겠다.

C++

 

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

using namespace std;

using mypair = pair<double, double>;

struct edge {
	int node1, node2;
	double cost;
};

vector<int> parent;

int find_parent(int curr) {
	if (curr == parent[curr])
		return curr;
	while (parent[curr] != curr)
		curr = parent[curr];
	return curr;
}

int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n;
	cin >> n;

	vector<mypair> vec(n);
	parent = vector<int>(n);

	for (int i = 0; i < n; ++i) {
		cin >> vec[i].first >> vec[i].second;
		parent[i] = i;
	}

	vector<edge> edges;
	auto get_cost = [](mypair a, mypair b) {return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2)); };

	for(int i=0;i<n;++i)
		for (int j = i + 1; j < n; ++j) {
			edges.push_back({ i,j,get_cost(vec[i],vec[j]) });
		}

	sort(edges.begin(), edges.end(), [](edge a, edge b) {return a.cost < b.cost; });

	double cost{};
	int cnt{};

	for (auto& e : edges) {
		int p1 = find_parent(e.node1), p2 = find_parent(e.node2);
		if (p1 == p2)
			continue;
		cost += e.cost;
		if (++cnt == n)
			break;
		if (p1 < p2)
			parent[p2] = p1;
		else
			parent[p1] = p2;
	}

	cout << cost;
	
	return 0;
}