C++[백준]1774번 우주신과의 교감

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

1774번: 우주신과의 교감

 

솔루션

---

최근에 유니온 파인드를 공부하면서 겪은 문제인데, 그 문제를 알고 있어서 그런가 접근은 생각보다 쉽게 가능했다.

 

다만 중간에 계산 실수가 있어서,, 디버깅 하는 데 좀 시간이 걸렸다.

 

먼저 우주신들의 갯수만큼 하나의 집합으로 설정하고,

 

M 개의 입력이 들어오는 동안에 두개의 집합의 거리를 0이라 가정하고 크루스칼을 사용한다.

 

그리고 M이 0인 경우에는 1번 인덱스를 기준으로 모든 거리에 대해서 pq에 넣어주었다.

 

그리고 크루스칼 알고리즘을 수행하면 풀린다.

 

 

 

다만, 이걸 푼다면 행성터널도 쉽게 풀 수 있지 않을까? 하는 생각이 든다.

 

 

 

코드

---

#define ll long long int
#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;

struct axis {
	int x, y;
};

struct axis arr[1002];

int N, M;

int parent[1002];
int getParent(int x) {
	if (x == parent[x]) return x;
	else return parent[x] = getParent(parent[x]);
}

void setUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a > b) parent[b] = a;
	else parent[a] = b;
}

bool isUnion(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	return a == b;
}

struct pa {
	int idx1, idx2;
	ll dis;
	bool operator< (const struct pa& t) const {
		if (dis == t.dis) {
			return idx1 > t.idx1;
		}
		return dis > t.dis;
	}
};
ll calcDis(struct axis& a, struct axis& b) {
	return (ll)(a.x - b.x) * (a.x - b.x) + (ll)(a.y - b.y) * (a.y - b.y);
}

priority_queue<struct pa> pq;

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

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		parent[i] = i;
		cin >> arr[i].x >> arr[i].y;
	}

	for (int i = 0; i < M; i++) {
		int idx1, idx2;
		cin >> idx1 >> idx2;
		pq.push({ min(idx1,idx2),max(idx1,idx2),0 });
	}

	if (pq.empty()) {
		for (int i = 2; i <= N; i++) {
			pq.push({ 1,i,calcDis(arr[0],arr[i]) });
		}
	}

	double sum = 0;
	while (!pq.empty()) {
		int idx1 = pq.top().idx1;
		int idx2 = pq.top().idx2;
		ll dis = pq.top().dis;
		pq.pop();

		if (isUnion(idx1, idx2)) continue;
		sum += sqrt(dis);
		setUnion(idx1, idx2);
		
		for (int i = 1; i <= N; i++) {
			if (isUnion(idx1, i)) {
				continue;
			}
			ll idx1Dis = calcDis(arr[idx1], arr[i]);
			ll idx2Dis = calcDis(arr[idx2], arr[i]);
			if (idx1Dis > idx2Dis)	 {
				pq.push({ idx2,i,idx2Dis });
			}
			else {
				pq.push({ idx1,i,idx1Dis });
			}
		}
	}
	cout << fixed;
	cout.precision(2);
	cout << sum << "\n";
}