[C/C++] 백준 1774번 - 우주신과의 교감 (MST, 크루스칼)

 

 

 

<코드>

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

int N, M;
int u, v, x, y;
int parent[1001];
double d, ans;
vector<pair<int, int>> GOD;
vector<tuple<double, int, int>> DIST;

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

bool union_node(int u, int v)
{
	u = find(u);
	v = find(v);

	// 부모 노드가 같다면 싸이클이	 생기므로 건너뜀
	if (u == v) return false;
	else
	{
		parent[u] = v; // 부모 노드 지정
		return true;
	}
}

double Cal_dist(int x1, int y1, int x2, int y2)
{
	double x_dist = pow(x1 - x2, 2);
	double y_dist = pow(y1 - y2, 2);

	return sqrt(x_dist + y_dist);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> M;

	// 자기 자신을 부모로 지정
	for (int i = 1; i <= N; i++)
		parent[i] = i;

	// 우주신들의 좌표 입력
	GOD.push_back({ 0,0 });
	for (int i = 1; i <= N; i++)
	{
		cin >> x >> y;
		GOD.push_back({x, y});
	}

	// 이미 연결된 통로들 입력
	for (int i = 1; i <= M; i++)
	{
		cin >> u >> v;
		union_node(u, v);
	}
	
	// i번 우주신과 j번 우주신 사이의 거리 계산
	for (int i = 1; i <= N - 1; i++)
	{
		for (int j = i + 1; j <= N; j++)
		{
			double r = Cal_dist(GOD[i].first, GOD[i].second, GOD[j].first, GOD[j].second);
			DIST.push_back({ r, i, j });
		}
	}

	sort(DIST.begin(), DIST.end());

	// MST 계산
	for (int i = 0; i < DIST.size(); i++)
	{
		x = get<1>(DIST[i]);
		y = get<2>(DIST[i]);
		d = get<0>(DIST[i]);
		if (union_node(x, y)) ans += d;		
	}

	//cout << ans << '\n';
	printf("%.2f", ans);
}

 

풀이 방법

가중치가 작은 순으로 정렬하여 싸이클이 발생하지 않도록 간선들을 추가해 나가면서 MST를 만드는 크루스칼 알고리즘을 이용하였습니다. 문제가 좀 어려워 아래의 블로그 풀이법을 참고하였습니다.

m.blog.naver.com/PostView.nhn?blogId=gydbslove&logNo=221595838218&proxyReferer=https:%2F%2Fwww.google.com%2F

 

 

 

 

www.acmicpc.net/problem/1774

1774번: 우주신과의 교감