4386 별자리 만들기 (골드 4)

이 문제는 모든 노드가 연결되어 있는 그래프에서 최소 스패닝 트리를 만드는 문제이다.

단, 간선의 가중치가 나와있지 않아서 이것만 미리 구해주면 된다.

 

 

 

이 문제를 풀면서 최소 스패닝 트리에 대해서 공부해보았는데, 

우선 스패닝 트리란 그래프 내의 모든 정점을 포함하는 트리이다.

따라서 최소 스패닝 트리는 그래프 내의 모든 정점을 포함하면서 간선들의 가중치 합이 최소여야 한다.

 

 

최소 스패닝 트리를 만드는 방법은 두 가지 방법이 있는데 나는 그 중 크루스칼 알고리즘을 사용했다.

크루스칼 알고리즘은 가중치를 오름차순으로 정렬한다음 맨 앞의 간선부터 연결해주면 된다.

근데 최소 스패닝 트리이므로 사이클이 생기면 안된다. 그래서 노드들의 부모를 확인해주고 부모가 서로 같다면 연결x, 다르다면 연결하는 방식으로 진행된다.

 

즉, 

1. 가중치가 가장 작은 간선 선택 후 노드 확인

2. 노드들의 부모를 찾음. -> find함수

3. 부모가 같다면 연결하지 않고 넘어감. 부모가 다르다면 최초 부모를 서로 연결해줌 -> Union 함수

이 3가지 단계를 반복해주면 된다.

 

 

// 별자리 만들기 (골드4)
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>

using namespace std;

pair<double, double>* arr;
vector<pair<double, pair<double, double>>> V;
int N;
int* parent;

void cal() {
	double cost;
	double x1, x2, y1, y2;

	for (int i = 0;i < N;i++) {
		for (int j = i + 1;j < N;j++) {
			x1 = arr[i].first; y1 = arr[i].second;
			x2 = arr[j].first; y2 = arr[j].second;

			cost = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));


			V.push_back(make_pair(cost, make_pair(i,j)));
		}
	}

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

	/*for (int i = 0;i < 3;i++) {
		cout << V[i].second.first << " " << V[i].second.second << " " << V[i].first << endl;
	}*/

	delete[] arr;

}

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

void Union(int x, int y) {
	x = find(x);
	y = find(y);

	parent[y] = x;
}


int main() {
	double Ans = 0;

	cin >> N;

	arr = new pair<double, double>[N];
	parent = new int[N];

	for (int i = 0;i < N;i++) {
		cin >> arr[i].first >> arr[i].second;
		parent[i] = i;
	}

	cal();
	
	//cout << endl << endl;

	for (int i = 0;i < V.size();i++) {
		//cout << V[i].second.first << " " << V[i].second.second << endl;
		if (find(V[i].second.first) != find(V[i].second.second)) {
			Union(V[i].second.first,V[i].second.second);
			Ans += V[i].first;
		}
	}

	cout.precision(3);
	cout << Ans;

	return 0;
}

// 2432KB, 0ms