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

www.acmicpc.net/problem/1774

1774번: 우주신과의 교감

 

 

 

알고리즘 종류

    - MST

    - Kruskal

 

 

 

사고 과정

    - 전형적인 MST 문제

    - 이미 연결된 간선을 구현하기 위해서 두 정점(v1, v2)에 union_find 알고리즘을 적용

 

 

 

구현(C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
int n, m;
 
int parents[1001];
 
vector<pair<int, int> > nodes;
vector<pair<pair<int, int>, double> > edges;
 
bool cmp(pair<pair<int, int>, double> a, pair<pair<int, int>, double> b){
    return a.second < b.second;
}
 
int get_parent(int x){
    if(parents[x] == x) return x;
    return parents[x] = get_parent(parents[x]);
}
 
void union_parent(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
void solution(){
    
    double dist;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(i == j) continue;
            dist = sqrt( pow(nodes[i].first - nodes[j].first, 2) + pow(nodes[i].second - nodes[j].second, 2) );
            edges.push_back({{i+1, j+1}, dist});
        }
    }
    
    sort(edges.begin(), edges.end(), cmp);
    
    double sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(get_parent(edges[i].first.first) != get_parent(edges[i].first.second)){
            sum += edges[i].second;
            union_parent(edges[i].first.first, edges[i].first.second);
        }
    }
    
    printf("%0.2f", sum);
}
 
int main(void){
    
    cin >> n >> m;
    
    for(int i=1; i<=n; i++) parents[i] = i;
    
    int y, x;
    for(int i=0; i<n; i++){
        cin >> y >> x;
        nodes.push_back({y, x});
    }
    
    // 이미 연결된 두 개의 정점을 연결하기(union_find) 
    int v1, v2;
    for(int i=0; i<m; i++){
        cin >> v1 >> v2;
        if(get_parent(v1) != get_parent(v2)) union_parent(v1, v2);
    }
    
    solution();
}
 

 

 

 

시행착오

    - 이미 연결된 정점들을 입력 받아서 union_find만 해버렸다. 조건으로 두 정점의 부모가 같은 지 확인을 하지 않았다. 왜냐하면, 예시에서 단 1개만 이미 연결된 정점으로 제시해서 큰 것이 들어와도 특별하지 않을 것 같았다. 실제로, m의 크기를 고려하지 않은 것은 아니다. 이미 연결된 정점의 쌍이 여러 개 입력되었을 때에 조건이 필요 없다고 생각했다. 계속 수정과 제출을 반복해도 되지 않아서 다른 사람의 해설에서 의심이 갔던 이 부분을 보았고 원인을 알 수 있었다. union-find을 적용할 때에는 두 정점의 부모가 같은 지 아닌 지 확인하는 과정이 같이 이루어져야 한다는 것을 배웠다.