[알고리즘] 백준 4386번: 별자리 만들기 (C++)

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

4386번: 별자리 만들기

별자리를 트리라고 생각했을 때, 거리 값이 비용 값이고, 총비용이 최소가 되게 구하려면 최소 스패닝 트리를 이용하면 된다.

생각을 해야 했던 부분은 각 별(노드)끼리의 거리였다. 복잡하게 생각할 필요 없이 2중 for문을 이용해 쌍방향으로 최소 스패닝 트리를 할 수 있도록 만들어주었다.

for(int i = 0; i < v.size(); i++){
    for(int j = 0; j < v.size(); j++){
        if(i == j) continue;
        dd dist = cal(i, j);
        edges.push_back({{i, j}, dist});
    }
}

거리를 계산하는 함수

dd cal(int i, int j){
    dd x = pow(v[i].first - v[j].first, 2);
    dd y = pow(v[i].second - v[j].second, 2);
    dd result = sqrt(x + y);
    return result;
}

---

[AC 코드]

#include <iostream>
#include <vector>
#include <utility>
#include <cmath>
#include <algorithm>
#define dd double
#define pdd pair<dd, dd>
#define MAX (100 + 1)
#define pii pair<int, int>
using namespace std;

vector<pdd> v;
vector<pair<pii, dd>> edges;
int parent[MAX];
int n;

dd cal(int i, int j){
    dd x = pow(v[i].first - v[j].first, 2);
    dd y = pow(v[i].second - v[j].second, 2);
    dd result = sqrt(x + y);
    return result;
}

bool cmp(pair<pii, dd> a, pair<pii, dd> b){
    return a.second < b.second;
}

int getRoot(int node) {
	if (node == parent[node]) return node;
	return parent[node] = getRoot(parent[node]);
}

bool find(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);

	if (rA != rB) return true;
	else return false;
}

void unionParent(int a, int b) {
	int rA = getRoot(a);
	int rB = getRoot(b);
	if (rA < rB) {
		parent[rB] = rA;
	}
	else {
		parent[rA] = rB;
	}
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        dd x, y;
        cin >> x >> y;
        v.push_back({x, y});
    }
    
    // 쉽게 접근할 수 있게 거리를 구하면서 다시 그래프 갱신
    for(int i = 0; i < v.size(); i++){
        for(int j = 0; j < v.size(); j++){
            if(i == j) continue;
            dd dist = cal(i, j);
            edges.push_back({{i, j}, dist});
        }
    }
    
    sort(edges.begin(), edges.end(), cmp);
    for(int i = 0; i <= n; i++){
        parent[i] = i;
    }
    
    dd result = 0;
    for(int i = 0; i < edges.size(); i++){
        if(find(edges[i].first.first, edges[i].first.second)){
            unionParent(edges[i].first.first, edges[i].first.second);
            result += edges[i].second;
        }
    }
    
    cout << fixed;
    cout.precision(6);
    cout << result;
    
    return 0;
}