[백준 10423번] 전기가 부족해 (C++)

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

10423번: 전기가 부족해

---

전기가 부족해 문제는 크루스칼/프림 알고리즘을 이용하여 해결할 수 있습니다.

 

모든 도시에 전기를 공급할 수 있도록 케이블을 설치하는 데 드는 최소 비용을 계산해야합니다.

따라서 발전소로부터 전기를 공급받는 그룹(G)에 모든 도시를 포함시켜야합니다.

 

발전소가 설치된 도시는 전기가 공급될 수 있기 때문에, 먼저, 그룹 G에 포함시킨 뒤, 비용이 낮은 간선부터 선택하여 모든 도시를 G에 포함시키면 됩니다.

 

아래는 크루스칼, Union Find를 이용한 코드입니다.

#include <bits/stdc++.h>
using namespace std;

#define G 0

vector<int> p(1010, -1);
int n, m, k; 

int find(int x){    // x의 그룹의 Root를 반환
    if(p[x] < 0) return x;
    return p[x] = find(p[x]);
}

bool is_diff_g(int u, int v){   // u와 v가 같은 그룹이면 false를 반환, 다른 그룹이면 union을 수행한 뒤 true를 반환
    u = find(u), v = find(v);
    if(u == v) return false;
    if(u == v) p[u] = v;
    else p[v] = u;
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for(int v, i = 0; i < k; i++){ // 발전소가 설치된 도시의 번호가 주어진다.
        cin >> v; 
        is_diff_g(G, v);  // 해당 도시를 G 그룹에 포함시킨다.
    }

    vector<tuple<int, int, int>> edges; // 간선을 저장하는 vector

    for(int i =0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        edges.push_back({w, u, v}); // 모든 간선을 edges에 추기
    }

    sort(edges.begin(), edges.end());   // 간선을 cost를 기준으로 정렬

    int ans = 0; // 모든 도시를 발전소에 연결시키기 위한 최소 비용
    int cnt = k;   // 그룹 G에 포함된 도시의 개수
    for(int i = 0; i < edges.size(); i++){  // 크루스칼 수행
        int w, u, v;
        tie(w, u, v) = edges[i];    
        if(!is_diff_g(u, v)) continue;  // u와 v가 같은 그룹인 경우 해당 간선을 선택하지 않음
        // u와 v가 서로 다른 간선인 경우, 해당 간선을 선택
        ans += w;   // 해당 간선의 비용을 더해줌
        cnt++;  // 그룹 G에 포함된 도시의 개수 증가
        if(cnt == n) break; // 모든 도시가 그룹 G에 포함된 경우 종료
    }
    cout << ans << "\n";
}