백준, boj) 1774. 우주신과의 교감 ( C / C++)

1. 문제 링크

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

1774번: 우주신과의 교감

2. 문제 개요

 주인공과 우주신들을 모두 연결해야 한다. 간접적으로 연결하여도 괜찮다. 이미 연결된 통로가 주어지고, 모두 연결하기 위한 통로길이의 합의 최솟값을 구해보자.

 

3. 문제 힌트

Kruskal 알고리즘을 사용해야한다.

(1) 그런데, 이미 연결된 통로가 있다. 이런 경우에는 어떻게 전처리를 해야 할까?

(2) 경로는 어떻게 구할까?

 

위의 두 가지 생각해야 할 점이 있다.

Kruskal알고리즘의 실행방식을 잘 생각해보자.

가중치 순서로 정렬해서 Union find를 사용해서 같은 그룹이면 pass 아니면 연결하고 같은 그룹 만들기..이다.

미리 연결된 통로들을 미리 묶어버리면 안 될까?

 

경로는 모두 연결해야 할까?

 

4. 문제 풀이

3번의 (1), (2)를 해결하면 이 문제를 쉽게 풀 수 있다.

우선, (2) 경로에 대해서 보자. 경로는 꼭 양방향일 필요는 없다. 그래서 반복문 2개를 써서 n^2의 형태가 아닌 n(n+1)/2만큼 연결해주자.

 

(1) 전처리에 대해서 살펴보자. 미리 연결된 애들만큼 연결해주자. (같은 그룹으로 만들어주자) 미리 연결된 간선만큼 연결해야 하는 간선에서 빼주자. 즉, n = 10일때(노드가10개일때) 연결해야하는 간선의 개수는 n-1, 즉 9개이다.

여기서 미리 연결되어있는 통로가 3개라면, 9-3 =6이고 6개만큼만 Kruskal알고리즘에서 연결해주면 된다. 물론 가중치가 가장 낮은 순서대로.

미리 연결한 통로를 또 연결하는 일 은 없다. 이미 같은 그룹으로 처리되어있기 때문에 무시하고 넘어간다.

 

거리 구할 때 오버플로우를 조심하자!!

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int n, m;
vector<pair<long long, pair<int, int>>> edge;	//cost, u, v
vector<pair<long long, long long>> v;	//x, y

struct disjointset {
	vector<int> root;

	void init(int size) {
		root.resize(size + 1);
		for (int i = 1; i <= size; ++i)
			root[i] = i;
		return;
	}

	int find(int x){
		if (root[x] == x)
			return x;
		return root[x] = find(root[x]);
	}

	bool merge(int x, int y) {
		x = find(x);
		y = find(y);

		if (x != y) {
			root[y] = x;
			return true;
		}
		else
			return false;
	}
}ds;


int main()
{
	scanf("%d %d", &n, &m);
	v.resize(n + 1);	

	for (int i = 1; i <= n; ++i) {
		long long x, y;
		scanf("%lld %lld", &x, &y);
		v[i] = { x,y };
	}
	//make a complete graph
	for (int i = 1; i < n; ++i) 
		for (int j = i + 1; j <= n; ++j) {
			long long dist = (v[j].first - v[i].first)*(v[j].first - v[i].first) + (v[j].second - v[i].second)*(v[j].second - v[i].second);
			edge.push_back({ dist,{i,j} });
		}
	sort(edge.begin(), edge.end());
	int cnt = 0;
	double ans = 0;
	ds.init(n + 1);

	for (int i = 0; i < m; ++i) {
		int from, to;
		scanf("%d %d", &from, &to);

		if (ds.merge(from, to)) 
			++cnt;
	}

	for (int i = 0; i < edge.size(); ++i) {

		if (cnt == n - 1)	break;

		if (ds.merge(edge[i].second.first, edge[i].second.second)) {
			++cnt;
			ans += sqrt(edge[i].first);
		}
	}

	printf("%.2lf", ans);
	return 0;
}

6. 결과 사진