[백준/C++] 별자리 만들기 (No. 4386)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

 

이 문제는 이름만 다르지 사실 이전에 풀었던 최소 스패닝 트리 문제와 다를게 없다.

 

 

왜냐하면 모든 별을 잇는 최소 비용을 계산하는게 목적인 문제이므로, 각 별 들을 잇는 간선의 비용을 계산해 어떤 별들을 잇는 간선인지 저장하면 MST 문제가 된다.

 

두 점의 거리를 계산하는 방법은 (x1, y1), (x2, y2) 일 경우 두 점의 거리 s^2 = (x1-x2)^2 + (y1-y2)^2 를 이용해 계산하면 된다.

 

 

이제 두 점의 거리를 계산하는 방법을 알았으므로, 크루스칼 알고리즘을 이용해 문제를 해결했다.

 

크루스칼 알고리즘은 Union-Find를 이용하는 방법이다.

 

Union Find를 이용하기 전에 아까 위에서 구한 간선들을 전부 비용을 기준으로 오름차순 정렬을 해준다.

 

그러면 항상 가장 먼저 나온 간선은 비용이 가장 적게 드는 간선이다.

 

이제 그 간선이 연결하는 두 별이 이미 이어져있는지 확인하면 간선을 추가할지 말지가 결정된다.

 

왜냐하면  비용을 기준으로 정렬을 했기 때문에, 두 별이 이미 이어져 있는 상태라면 현재 간선보다 더 적은 비용의 간선을 이용해 연결된 상태기 때문이다.

 

여기서 두 별이 이어져 있는지를 Union-find를 이용해 확인한다.

 

두 별이 같은 집합에 속해있다면, 이미 연결된 상태다.

만약 두 별이 각자 다른 집합에 속해있다면, 연결되지 않았다는 뜻이다.

 

그러므로 두 점이 속한 집합이 다르면 서로 연결되지 않았으므로 두 집합을 연결해 주면 된다.

(한쪽 집합의 대표원소( parents )를 다른 집합의 대표원소( parents )로 바꿔주면 된다. )

 

최종적으로 모든 별들이 연결이 되면 그 때 비용을 출력하면 된다.

 

 

​

[아이디어 정리]

1. 별들 사이의 비용을 계산해 비용을 기준으로 오름차순 정렬을 한다. (또는 priority_queue를 이용한다.)
2. 간선을 꺼내고 이 간선이 잇는 별들이 같은 집합에 속해있다면, 이미 연결된 상태이므로 다음 간선으로 넘어간다.
3. 만약 간선이 잇는 별들이 다른 집합에 속해있다면, 두 집합을 합치고 간선의 비용을 추가한다.
4. 모든 간선의 비교가 끝나면 최종적으로 소모된 비용을 출력한다.

 

 

 

Code

 

 

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

struct st {
	int s;
	int e;
	float co;
};

struct cmp {
	bool operator ()(st a, st b) {
		return a.co > b.co;
	}
};

int FindPar(vector<int>& par, int n) {
	if (par[n] == n) {
		return n;
	}
	return par[n] = FindPar(par, par[n]);
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	float x, y;
	int n;
	scanf("%d", &n);
	vector<pair<float, float>> v(n);
	float tmp;
	priority_queue<st,vector<st>, cmp> q;
	st ST;
	for (int i = 0; i < n; i++) {
		scanf("%f%f", &x, &y);
		v[i] = make_pair(x, y);
		for (int j = 0; j < i; j++) {
			ST.co = pow(pow(v[i].first - v[j].first, 2) + pow(v[i].second - v[j].second, 2), 0.5);
			ST.s = i, ST.e = j;
			q.push(ST);
		}
	}

	vector<int> par(n);
	int pa, pb;
	float answer=0;
	for (int i = 0; i < n; i++)
		par[i] = i;
	while (!q.empty()) {
		ST = q.top();
		q.pop();
		pa = FindPar(par, ST.s), pb = FindPar(par, ST.e);
		if (pa != pb) {
			par[pa] = pb;
			answer += ST.co;
		}
	}
	printf("%.2f", answer);
	return 0;
}

 

---

어제는 Prim 알고리즘으로 풀었으니까 오늘은 크루스칼 알고리즘을 이용해 풀어봤다.

이전에 풀었던 문제와 비슷해서 딱히 어렵지는 않았다...

 

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