문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

• 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
• 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10^(-2)까지 허용한다.

예제

---

풀이

일반적인 크루스칼 알고리즘 문제인데, 간선의 비용만 우리가 직접 구해주면 된다.

처음 시도 (조합)

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm>
#include <cmath>
#define MAX 1001 
using namespace std;

int n; // 별의 개수 
vector<pair<float, float>> v; // 별의 좌표 
vector<pair<float, pair<int, int>>> edges; // 정점 a와 b 사이의 거리 c
int parent[MAX]; // 루트 노드를 저장하는 테이블 
float result = 0; // 최소 비용 

// 특정 원소가 속한 집합 찾아내기 
int findParent(int x){
	// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출 
	if(x == parent[x]) return x; 
	return parent[x] = findParent(parent[x]);
}

// 두 원소가 속한 집합을 합치기 
void unionParent(int a, int b){
	a = findParent(a);
	b = findParent(b);

	// 더 작은 번호가 부모 노드가 되도록 
	if(a < b) parent[b] = a;
	else parent[a] = b; 
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n; 
	
	// 부모 테이블 초기화 
	for(int i = 0; i < n; i++){
		parent[i] = i; 
	}

	// 별의 좌표 저장하기 
	for(int i = 0; i < n; i++){
		float x, y; 
		cin >> x >> y; 
		v.push_back({x, y}); 
	}

	// n개 중에 2개 선택 
	vector<bool> selected(n, true); 

	// 오름차순 정렬된 bool 배열을 만들기 위해 
	// 앞의 n-2개는 false, 뒤의 2개는 true로 표시 
	for(int i = 0; i < n - 2; i++){ 
		selected[i] = false; 
	}

	// 선택된 두 정점의 번호와 좌표 저장 
	vector<pair<int, pair<float, float>>> nodes; 
	do{
		for(int i = 0; i < n; i++){
			if(selected[i]){
				nodes.push_back({i, {v[i].first, v[i].second}});
			}
		}

		// 선택된 두 정점 간의 거리 구하기 
		float x1 = nodes[0].second.first; 
		float y1 = nodes[0].second.second; 
		float x2 = nodes[1].second.first; 
		float y2 = nodes[1].second.second; 
		float cost = sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
	
		// 선택된 두 정점 간의 거리와 번호 저장 
		edges.push_back({cost, {nodes[0].first, nodes[1].first}});
		
	}while(next_permutation(selected.begin(), selected.end()));
	
	// 간선을 비용 순으로 정렬 
	sort(edges.begin(), edges.end()); 

	// 간선을 하나씩 확인하면서 
	for(int i = 0; i < edges.size(); i++){
		float cost = edges[i].first; 
		int a = edges[i].second.first; 
		int b = edges[i].second.second; 

		// 사이클이 발생하지 않는 경우에만 MST에 포함시키기 
		if(findParent(a) != findParent(b)){
			unionParent(a, b); 
			result += cost; 
		}
	}

	cout << result; 

	return 0; 
}

답안

https://yabmoons.tistory.com/404

복잡하게 n개 중에 2개를 선택하는 조합 알고리즘을 사용할 필요 없이, 그냥 첫번째 정점을 i라고 하면 두번째 정점은 i+1로 선택하면 되는 거였다!!! 인접한 두 정점을 선택하여 거리를 구하면 그게 곧 간선의 가중치가 된다. 그 값으로 크루스칼 알고리즘을 적용하면 된다.

#include <iostream>
#include <vector>
#include <utility> 
#include <algorithm>
#include <cmath>
#define MAX 1001 
using namespace std;

int n; // 별의 개수 
int parent[MAX]; // 루트 노드를 저장하는 테이블 
vector<pair<float, float>> coord; // 별의 좌표 
vector<pair<float, pair<int, int>>> edges; // 정점 a와 b 사이의 거리 c
float result = 0; // 최소 비용 

// 특정 원소가 속한 집합 찾아내기 
int findParent(int x){
	// 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출 
	if(x == parent[x]) return x; 
	return parent[x] = findParent(parent[x]);
}

// 두 원소가 속한 집합을 합치기 
void unionParent(int a, int b){
	a = findParent(a);
	b = findParent(b);

	// 더 작은 번호가 부모 노드가 되도록 
	if(a < b) parent[b] = a;
	else parent[a] = b; 
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n; // 별의 개수 
	
	for(int i = 0; i < n; i++){
		parent[i] = i; // 부모 테이블 초기화 
	}

	for(int i = 0; i < n; i++){
		float x, y; 
		cin >> x >> y; 
		coord.push_back({x, y}); // 별의 좌표 
	}

	for(int i = 0; i < n; i++){
		float x1 = coord[i].first; 
		float y1 = coord[i].second; 

		for(int j = i + 1; j < n; j++){
			float x2 = coord[j].first; 
			float y2 = coord[j].second; 
            
            // 두 정점 사이의 거리 구하기 
			float dist = sqrt(pow(x1-x2, 2) + pow(y1-y2, 2));
			edges.push_back({dist, {i, j}}); 
		}
	}

	// 간선의 비용에 따라 오름차순 정렬 
	sort(edges.begin(), edges.end()); 

	for(int i = 0; i < edges.size(); i++){
		float cost = edges[i].first; 
		int a = edges[i].second.first; 
		int b = edges[i].second.second; 
        
		if(findParent(a) != findParent(b)){
			unionParent(a, b);
			result += cost; 
		}
	}

	cout << result; 

	return 0; 
}