[백준][C++] 전기가 부족해

www.acmicpc.net/problem/10423

10423번: 전기가 부족해

 

 

 

알고리즘 종류

    - MST

 

 

 

사고 과정

    - 발전소 노드의 부모를 하나로 통일한다. 통일할 노드는 발전소 노드들 중에 가장 작은 노드이다. 이렇게 해결한 이유는 다음과 같다. 일반적인 Kruskal은 하나의 부모 노드로 통일하기 때문에 그래프가 1개 나온다. 하지만, 여기서는 부분 그래프가 나온다. 그래프가 여러 개 나오기 위해서는 부모가 여러 개면 된다.

 

 

 

구현(C++)

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M, K;
vector<pair<pair<int, int>, int> > edges;
int parents[1001];
 
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second < b.second;
}
 
int getParent(int x){
    if(parents[x] == x) return x;
    return parents[x] = getParent(parents[x]);
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a > b) parents[b] = a;
    else parents[a] = b;
}
 
void solution(){
    
    sort(edges.begin(), edges.end(), cmp);
 
    int sum=0;
    for(int i=0; i<edges.size(); i++){
        if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
            sum += edges[i].second;
            unionParents(edges[i].first.first, edges[i].first.second);
        }
    }
    cout << sum;
}
 
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N >> M >> K;
    for(int i=1; i<=N; i++) parents[i] = i;
    
    // 발전소 노드의 부모를 모두 1개로 
    int p;
    cin >> p;
    parents[p] = p;
    for(int i=0; i<K-1; i++){
        int ps;
        cin >> ps;
        parents[ps] = p; 
    }
    
    int u, v, w;
    for(int i=0; i<M; i++){
        cin >> u >> v >> w;
        edges.push_back({{u, v}, w});
    }
    
    solution();
}

 

 

 

시행착오