[백준] 1197번 : 최소 스패닝 트리 c++ 풀이

접근:

이름 부터 최소 스패닝 트리를 구하는 문제

이에 대한 알고리즘은 prim 알고리즘과 kruskal 알고리즘이 유명하다

 

전략:

prim보다는 krusal이 조금 더 접근하기 쉬울 것 같아서 선택했으나, 둘 중 뭘 선택 해도 상관은 없다.

간선을 가중치가 낮은 순서대로 정렬을 한 후에, 작은 것부터 하나씩 tree에 추가한다.

추가할 때는 사이클이 발생하지 않도록 해야하기 때문에, 간선을 추가하려고 할때 두 정점이 같은 집합인지를 확인한다.

같은 집합이라면 패스하고 다음 간선을 조사한다.

n-1번이 추가되면 종료한다.

(다만 다음 코드 상에는 딱히 최적화를 진행하지 않고,  전체 조사를 하도록 하였다.)

 

구현:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge{
    int start;
    int end;
    int weight;
};

bool comp(Edge a, Edge b){
    if(a.weight == b.weight) return a.start < b.start;
    return a.weight < b.weight;
}

int v, e;
int mst_weight = 0;
vector<int> group;
vector<Edge> ed;

int find_group(int x) // 그룹 찾기
{
    if(group[x] == x) return x; //본인이 리더이면 반환
    else return group[x] = find_group(group[x]); //본인이 리더가 아니면, 본인이 가리키는 요소를 다시 조사하여 리더를 본인에게 대입한다. 
}

bool same_group(int x, int y) //같은 그룹 확인
{
    x= find_group(x);
    y = find_group(y);
    if(x==y) return true;
    else return false;
}

void union_group(int x, int y){ //그룹 합치기
    x = find_group(x);
    y = find_group(y);
    (x!=y)?group[y]=x:0; //그룹이 다르면, x의 리더를 대입
}

int main(){
    cin >> v >> e;
    group.resize(v+1);

    for(int i=0;i<e;i++){
        int a,b,c;
        cin >> a >> b >> c;// a -> b (with c weight (c < 0 is possible))
        ed.push_back({a,b,c});
    }
    for(int i=0;i<=v;i++){ // 그룹 초기화
        group[i] = i;
    }
    
    sort(ed.begin(), ed.end(),comp); //간선을 가중치 순서로 배열
    
    
    for(auto t : ed){ //간선 찾기
        if(!same_group(t.start, t.end)){ //같은 그룹이 아니면
            union_group(t.start, t.end); // 그룹 통합
            mst_weight += t.weight; //가중치 더하기
        }
    }

    cout << mst_weight << '\n';
    return 0;
}