[백준/BOJ] 백준 10021번 : Watering the Fields

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

10021번: Watering the Fields

 

점들 사이의 비용이 c이상이면, 해당 점들 사이에 간선(파이프)을 추가해서, 만들어진 간선을 이용해 최소 스패닝 트리를 만들어 문제를 해결했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int n, c;
vector<pair<int, int>> point;
vector<tuple<int, int, int>> edge; //(비용, 위치 1, 위치 2)
vector<int> parent(2005, 0);
vector<int> rank_size(2005, 0);
int result = 0;

void init() {
	for (int i = 0; i < 2005; i++) {
		parent[i] = i;
		rank_size[i] = 1;
	}
}

int find(int u) {
	if (parent[u] == u) {
		return u;
	}

	return parent[u] = find(parent[u]);
}

void merge(int u, int v) {
	u = find(u);
	v = find(v);

	if (u == v) {
		return;
	}

	if (rank_size[u] < rank_size[v]) {
		parent[u] = v;
	}

	else {
		parent[v] = u;
		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}
}

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

	init();

	cin >> n >> c;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;

		point.push_back(make_pair(x, y));
	}

	//점의 위치를 통해 각 점들간의 간선을 구한다
	for (int i = 0; i < point.size(); i++) {
		for (int j = 0; j < point.size(); j++) {
			if (i == j) {
				continue;
			}

			int cost = ((point[i].first - point[j].first) * (point[i].first - point[j].first)) + ((point[i].second - point[j].second) * (point[i].second - point[j].second));

			// 비용이 c 이상인 간선만 추가한다
			if (cost >= c) {
				edge.push_back(make_tuple(cost, i, j));
			}
		}
	}

	// 비용 오름차순으로 정렬
	sort(edge.begin(), edge.end());

	// 최소 스패닝 트리를 통해, 최소 비용을 구한다
	int maked_cnt = 0; //만들어진 최소 스패닝 트리의 간선의 개수
	for (int i = 0; i < edge.size(); i++) {

		int cost = get<0>(edge[i]);
		int u = get<1>(edge[i]);
		int v = get<2>(edge[i]);

		u = find(u);
		v = find(v);

		if (u == v) {
			continue;
		}

		merge(u, v); //같은 그룹으로 합치기
		maked_cnt++;
		result += cost;

		if (maked_cnt == n - 1) { //최소 스패닝 트리가 만들어졌을때
			break;
		}
	}

	if (maked_cnt != n - 1) { //최소 스패닝 트리가 만들어지지 않았을때
		cout << -1 << "\n";
	}
	else {
		cout << result << "\n";
	}

	return 0;
}