[C++][Graph] 백준 1197번 문제 풀이 및 설명

 

 

백준 1197번 문제는 MST( Minimum - Spanning -Tree )를 구하는 문제이다.

 

 

알고리듬으로 Union - Find 를 이용하여 구하면 간단하게 구할 수 있다.

 

 

 

문제

 

 

 

 

 

알고리듬

 

① 입력 Edge들을 먼저 가중치 기준으로 오름차순 정렬 한다.

 

- 정수 A,B,C 를 tuple 사용하여 묶어서 vector에 저장

- algorithm stl의 sort 함수 사용 (가중치 기준 정렬이므로 cmp 함수 추가)

 

② 정렬된 Edge들을 하나씩 꺼내며 싸이클이 생기는 지 확인 (Tree 이기 때문에 싸이클이 생기면 안됨)

 

- 정렬된 edge들을 하나씩 꺼내며 정수 A,B의 find 값이 같은 지 확인

- 같다면 Union(A,B) 해주고 다르다면 무시

- 같을 때 Union 해주면서 그 edge의 weight를 total에 더해줌.

 

 

 

Code

 

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

using namespace std;

int* root;

int find(int num){

    if(root[num]==num) return num;

    return find(root[num]);
}

void union_(int a , int b){
    
    a = find(a);
    b = find(b);

    root[b] = a;

}

static bool CmpWeight(tuple<int,int,int> &t1 , tuple<int,int,int> &t2 ){
    return get<2>(t1) < get<2>(t2);
}

int main(int argc , char** argv){

    vector<tuple<int , int , int>> v;

    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    int V , E;

    cin >> V >> E;
	
    root = new int [V+1];
    for(int i = 0 ; i < V+1; ++i) root[i] = i;
    
    int A , B , C;
    int total = 0;


    for(int i = 0 ;i < E ; ++i){
        cin >> A >> B >> C;

        v.push_back(make_tuple(A,B,C));

    }

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

    for(int i = 0 ; i <v.size() ; ++i){
        
        A = get<0>(v[i]);
        B = get<1>(v[i]);
        C = get<2>(v[i]);
        
        if(find(A) != find(B)){
            union_(A,B);
            total += C;
        }

    }

    cout << total;
    
    delete[] root;
}