[백준 1774] 우주신과의 교감 C++

1774번: 우주신과의 교감

최소 스패닝 트리

---

 

Minimum Spanning Tree (MST) - Kruskal

 

통로의 개수 1000개

 

이미 연결이 되어있다고 입력받은 노드들끼리는 Union_Node를 수행한다.

 

adj 배열을 간선의 거리가 짧은 순으로 정렬한다.

 

adj배열의 원소를 하나씩 보면서 adj원소에 저장된 두 정점을 Union_Node해준다.

 

이미 M개의 간선들에 대해서 Union_Node를 했고, 해당 간선들을 거리를 0으로 취급하면 되게 때문에 간선을 구한 횟수가 N-1-M 번이 되면 for문을 종료한다.

 

주의할 점.

x와 y의 좌표가 최대 1,000,000 이므로 거리를 구하기 위해서 제곱을 하면 int의 범위를 넘어갈 수가 있다.

long long 자료형으로 바꾸자.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
#define pdi pair<double, int>
typedef long long ll;
#define pll pair<ll, ll>
 
// typedef pair<int, int> pii;
 
using namespace std;
 
struct Line{
    ll st;
    ll ed;
    double len;
};
 
int N, M;
pll SpaceGod[1001];
int Node[1001];
vector<Line> adj;
 
bool cmp(Line &a, Line &b){
    return a.len < b.len;
}
 
int findtopnode(int a){
    if(Node[a] < 0) return a;
    return Node[a] = findtopnode(Node[a]);
}
 
bool Union_Node(int a, int b){
    a = findtopnode(a);
    b = findtopnode(b);
    
    if(a == b) return false;
    
    if(Node[a] < Node[b]){
        Node[a] += Node[b];
        Node[b] = a;
    }
    else{
        Node[b] += Node[a];
        Node[a] = b;
    }
    return true;
}
 
void input(){
    cin >> N >> M;
    ll x, y;
    for(int i = 1; i <= N; i++){
        cin >> x >> y;
        SpaceGod[i] = {x, y};
    }
    
    memset(Node, -1, sizeof(Node));
    
    for(int i = 0; i < M; i++){
        cin >> x >> y;
        Union_Node(x, y);
    }
}
 
double dist(pll &a, pll &b){
    return sqrt(pow(abs(a.first - b.first), 2) + pow(abs(a.second - b.second), 2));
}
 
void solve(){
    for(int i = 1; i <= N-1; i++){
        for(int j = i+1; j <= N; j++){
            if(findtopnode(i) == findtopnode(j)) continue;
            adj.push_back({i, j, dist(SpaceGod[i], SpaceGod[j])});
        }
    }
    
    sort(adj.begin(), adj.end(), cmp);
    
    int cnt = 0;
    double ans = 0;
    
    for(int i = 0; i < adj.size(); i++){
        ll u = adj[i].st;
        ll v = adj[i].ed;
        double leng = adj[i].len;
        if(Union_Node(u, v)){
            ans += leng;
            cnt++;
        }
        if(cnt == N-1-M) break;
    }
    
    printf("%.2f", ans);
}
 
int main(){
    input();
    solve();
    
    return 0;
}