[C++] 백준 4343번: Arctic Network

문제 링크

4343번: Arctic Network

문제 요약

P개의 전진기지들을 모두 연결해야 한다. 이때, 두 전진기지가 통신하기 위해서는, 전진기지 사이의 거리만큼의 힘을 필요로 한다. 이때, 필요한 힘의 최솟값을 구해야 한다.
또, S개의 전진기지에 위성 채널을 설치할 수 있는데, 위성 채널이 있는 전진기지끼리는 위성을 통해 통신할 수 있다.

접근 방법

지문을 제대로 이해하지 못해서 많이 틀렸던 문제였습니다. 자그마치 7개월 전에 풀다가 이해가 안되서 포기했었는데, 오늘 다시 잡아봤습니다.

크루스칼 알고리즘으로 MST를 구하면서 MST에 포함되는 간선의 가중치들을 모두 저장해줍니다. 이 가중치들은 자동적으로 오름차순으로 저장됩니다. 이때 뒤에서부터 S번째 가중치를 출력해주면 됩니다.

MST에서 가중치가 큰 간선으로 연결된 정점들부터 위성을 설치해줍니다. 그랬을때, 남은 간선 중에 가중치의 최댓값이 정답이 됩니다.

S개의 정점에 위성을 설치하면 제외되는 간선의 수는 S - 1개라는 점을 잘 생각해야 합니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 501;
int parent[MAX];

struct Edge {
	int v1, v2;
	double weight;

	bool operator<(const Edge& a) { return weight < a.weight; }
};

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

int Find(int a) {
	if (a == parent[a])
		return a;
	return parent[a] = Find(parent[a]);
}

void Union(int a, int b) {
	int pa = Find(a), pb = Find(b);
	parent[pa] = pb;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	while (n--) {
		int s, p;
		cin >> s >> p;

		init(p);
	
		vector<pair<int, int>> v(p + 1);
		for (int i = 1; i <= p; i++)
			cin >> v[i].first >> v[i].second;
		 
		vector<Edge> edges;
		for (int i = 1; i <= p; i++)
			for (int j = i + 1; j <= p; j++)
				edges.push_back({ i, j, sqrt(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2)) });

		sort(edges.begin(), edges.end());
		
		vector<double> res;
		for (auto& i : edges) {
			if (Find(i.v1) != Find(i.v2)) {
				Union(i.v1, i.v2);
				res.push_back(i.weight);
			}
		}

		cout << fixed;
		cout.precision(2);
		cout << res[res.size() - s] << '\n';
	}

	return 0;
}