[c++][백준 21924][최소 신장 트리][MST] 도시 건설 - 컴도리돌이

---

 

21924번: 도시 건설

---

풀이 과정

 

알고리즘 코딩 문제를 어느 정도 풀었으면 해당 문제에서 예로 사용한 그림만 봐도 최소 신장 트리 알고리즘으로 풀어야한다는 것을 단번에 알 수 있을것이다. 여기서 최소 신장 트리는 그래프 내의 모든 정점을 포함하는 트리중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 최소 신장트리는 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것이 아니라, 간선에 가중치를 고려하여 최소 비용의 신장 트리를 선택하는 것을 말한다. 즉 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다.

 

주의 사항

 

가중치 값이 적지 않기 때문에 모든 값을 long long으로 처리해 줬다... 만약 맞왜틀이라면 자료형을 고려해보자..

그리고 해당 문제는 예산을 얼마나 절약할 수 있는지이다..!!

---

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

long long n,m,totalCost = 0;


vector<pair<int,pair<int,int>>> v;
vector<int> root;

void init(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

void input(){
    cin >> n >> m;

    root.resize(n+1,0);
    for(int i=0,a,b,c; i<m ;i++){
        cin >> a >> b >> c;
        v.push_back({c,{a,b}});
        totalCost += c;
    }
}

int find(long long x){
    if(root[x] == x) return x;
    else return root[x] = find(root[x]);
}
void UNION(long long x,long long y){
    x = find(x);
    y = find(y);

    if(x != y) root[y] = x;
}

bool SAMEROOT(long long x,long long y){
    x = find(x);
    y = find(y);

    if(x == y) return true;
    else return false;
}

void solution(){

    init();
    input();

    sort(v.begin(),v.end());

    for(int i=1; i<=n ;i++) root[i] = i;
    long long answer = 0,cnt = 0;
    for(auto vv : v){
        int a = vv.second.first;
        int b = vv.second.second;
        int c = vv.first;

        if(!SAMEROOT(a,b)){
            UNION(a,b);
            totalCost -= c;
            cnt ++;
            if(cnt == n-1) break;
        }
    }
    if(cnt != n-1) cout << -1;
    else cout << totalCost;
}

int main(){
    solution();

    return 0;
}