[백준][C++] 1368 물대기

www.acmicpc.net/problem/1368

1368번: 물대기

 

 

 

알고리즘 종류

MST

크루스칼

 

 

사고 과정

'논 사이 연결 VS 논에 우물파기'를 비교해야 하는 문제입니다. 생각해보면, 트리가 여러 개 나올 수 있다는 것을 알 수 있습니다. 이럴 경우, 가상의 노드를 생성하여 해결할 수 있습니다. 즉, 가상의 노드 0을 만들고 0과 연결된 간선을 우물을 파는 비용으로 하면 됩니다. 아래 그림으로 설명해드리겠습니다.

 

우선 초기 상태입니다. 붉은색은 우물을 파는 비용, 주황색은 논을 연결하는 비용입니다.

 

이제 가상의 노드 0으로 연결하겠습니다. 우물을 파는 비용인 붉은색은 그대로 0번과 연결된 간선의 비용이 됩니다. 이제 일반전인 MST 알고리즘을 적용하면 됩니다.

 

이렇게 가상의 노드를 만드는 방법과 유사한 문제가 있습니다. 이것입니다. 알고리즘 유형은 최단경로이지만 마찬가지로 가상의 노드를 만들어서 문제를 해결합니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int n;
 
int mat[301][301];
int parents[301];
vector<pair<int, pair<int, int> > > edges;
 
 
bool cmp(pair<int, pair<int, int> > a,  pair<int, pair<int, int> > b){
    return a.first < b.first;
}
 
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
 
void union_parents(int a, int b){
    a = get_parent(a);
    b = get_parent(b);
    
    if(a > b) parents[a] = b;
    else parents[b] = a;
}
 
 
void solution(){
    
    sort(edges.begin(), edges.end(), cmp);
    for(int i=0; i<=n; i++) parents[i] = i;
    
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        int node1 = edges[i].second.first;
        int node2 = edges[i].second.second;
        int cost = edges[i].first;
        
        if(get_parent(node1) != get_parent(node2)){
            union_parents(node1, node2);
            sum += cost;
        }
    }
    
    cout << sum << endl;
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    
    int cost;
    for(int i=1; i<=n; i++){
        cin >> cost;
        edges.push_back({cost, {0, i}});
    }
        
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> mat[i][j];
        }
    }
    
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++){
            edges.push_back({mat[i][j], {i, j}});
        }
    }
    
    solution();
}

 

 

 

시행착오