์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ํฌ๋ฃจ์Šค์นผ
  • ๋ชจ๋“  ํ•„๋“œ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•˜๊ณ , ์–‘ ์ชฝ ํ•„๋“œ์˜ ๋ฒˆํ˜ธ์™€ ๊ฑฐ๋ฆฌ๋ฅผ ๋ฒกํ„ฐ์— ์ €์žฅํ•œ๋‹ค.
  • ๊ฑฐ๋ฆฌ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๊ณ , ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์‹œํ–‰
  • ์ด๋•Œ, ๋‹จ์ˆœํžˆ union-find ์•Œ๊ณ ๋ฆฌ์ฆ˜์œผ๋กœ ํ•˜๋ฉด find์—์„œ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚œ๋‹ค.
  • ๋”ฐ๋ผ์„œ set์„ ํ™œ์šฉํ•ด์„œ ํฌ๋ฃจ์Šค์นผ์„ ํ•˜๋ฉด ๋œ๋‹ค.

ํ—ค๋งจ ์ง€์ 

  1. set์„ ์ด์šฉํ•ด์„œ ํ• ๋•Œ, ์„œ๋กœ ๋‹ค๋ฅธ ์ง‘ํ•ฉ์ด์—ˆ๋‹ค๊ฐ€ ํ•ฉ์ณ์งˆ๋•Œ, ํ•˜๋‚˜๋งŒ ์˜ฎ๊ธฐ๋ฉด ์•ˆ๋œ๋‹ค. ๊ทธ set์— ์†ํ•ด์žˆ๋Š” ๋ชจ๋“  ์ ์„ ๋‹ค ์˜ฎ๊ฒจ์•ผํ•จ
  2. ๊ผญ ์ฒซ๋ฒˆ์งธ ์ง‘ํ•ฉ์œผ๋กœ ํ•ฉ์ณ์ง€์ง€ ์•Š๋Š”๋‹ค. ๋”ฐ๋ผ์„œ, ๋ชจ๋“  ์ ๋“ค์ด ๊ฐ™์€ ์ง‘ํ•ฉ์— ์žˆ๋Š”์ง€ ํ•˜๋‚˜ํ•˜๋‚˜ ํ™•์ธํ•ด๋ด์•ผํ•œ๋‹ค.

์ฝ”๋“œ

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
 
struct node {
	int first;
	int second;
	int length;
 
	bool operator< (node a) {
		return length < a.length;
	}
};
 
vector<pair<int, int>> field;
vector<node> lengths;
vector<set<int>> unionset;
int N, C, parent[2000];
long long result;
 
void calcLengths();
bool kruskal();
int power(int a) {
	return a * a;
}
 
int main() {
	cin >> N >> C;
	int a, b;
	while (N--) {
		cin >> a >> b;
		field.push_back({ a, b });
	}
	N = field.size();
 
	calcLengths();
	memset(parent, -1, sizeof(parent));
	sort(lengths.begin(), lengths.end());
 
	if (kruskal())
		cout << result;
	else
		cout << "-1";
}
 
void calcLengths() {
	for (int i = 0; i < N; i++)
		for (int j = i + 1; j < N; j++)
			lengths.push_back({ i, j, power((field[i].first - field[j].first)) + power((field[i].second - field[j].second)) });
}
 
bool kruskal() {
	for (int i = 0; i < lengths.size(); i++) {
		int f = lengths[i].first, s = lengths[i].second, l = lengths[i].length;
		int sp = parent[s], fp = parent[f];
		if (l < C)
			continue;
 
		if (fp == -1 && sp == -1) {
			set<int> t;
			t.insert(f);
			t.insert(s);
			unionset.push_back(t);
			parent[f] = unionset.size()-1;
			parent[s] = parent[f];
			result += l;
		}
		else if (fp == -1) {
			unionset[sp].insert(f);
			parent[f] = sp;
			result += l;
		}
		else if (sp == -1) {
			unionset[fp].insert(s);
			parent[s] = fp;
			result += l;
		}
		else if(fp != sp) {
			for (auto iter = unionset[sp].begin(); iter != unionset[sp].end(); iter++) {
				parent[*iter] = fp;
				unionset[fp].insert(*iter);
			}
				result += l;
			unionset[sp].clear();
		}
	}
	int root = parent[0];
	for (int i = 0; i < N; i++) {
		if (parent[i] != root)
			return false;
	}
 
	return true;
}