[백준/BOJ] 백준 14167번 : Moocast

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

14167번: Moocast

 

소들 사이를 연결하는 간선을 만들어, 이를 이용해 최소 스패닝 트리를 만들면서, 최소 스패닝 트리에서 가장 긴 간선의 길이를 구하는 방법으로 문제를 해결했다.

 

코드

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

int n;
vector<pair<int, int>> cow;
vector<tuple<int, int, int>> edge; //(노드간 거리의 제곱, 노드1, 노드2)
int parent[1005];
int rank_size[1005];

void pre() {
	for (int i = 0; i < 1005; 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);

	pre();

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		cow.push_back(make_pair(x, y));
	}

	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int u = i;
			int v = j;
			int dist = ((cow[u].first - cow[v].first)*(cow[u].first - cow[v].first)) + ((cow[u].second - cow[v].second)*(cow[u].second - cow[v].second));
			edge.push_back(make_tuple(dist, u, v));
		}
	}

	int result = 0;
	int cnt = 0;
	sort(edge.begin(), edge.end());
	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]);

		if (find(u) != find(v)) {
			merge(u, v);
			cnt++;
			result = max(result, cost);
		}

		if (cnt == n - 1) {
			break;
		}
	}

	cout << result;

	return 0;
}