[백준 1197번] 최소 스패닝 트리 (C++)

문제링크 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

struct p
{
    int u, v, weight;
    bool operator<(p const &e) //가중치가 작은 것부터
    {
        return weight < e.weight;
    }
};

int V, E, result;
int parent[10001];
vector<p>v;

int find_root(int x) //부모찾기
{
    if(x == parent[x]) return x;
    return parent[x] = find_root(parent[x]);
}

bool check(int a, int b) //이어졌는가?
{
    a=find_root(a);
    b=find_root(b);
    if(a==b) return 1;
    return 0;
}

void Union(int a, int b) //병합
{
    a=find_root(a);
    b=find_root(b);
    parent[b]=a;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> V >> E;
    for(int i=0; i<E; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({a, b, c});
    }

    for(int i=1; i<=V; i++) //부모 초기화
    {
        parent[i] = i;
    }

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

    for(int i=0; i<E; i++)
    {
        if (!check(v[i].u, v[i].v)) //부모가 다르면 (이어져있지 않다면)
        {
            Union(v[i].u, v[i].v); //간선 이어주기
            result += v[i].weight; //가중치 합산
        }
    }

    cout << result;

    return 0;
}

크루스컬이나 프림 알고리즘으로 풀 수 있는 최소 스패닝 트리 (MST) 문제이다.

나는 크루스컬 알고리즘을 사용하였다.

 

기본적으로 크루스컬 알고리즘은 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘이다.

여기서 최소 신장 트리는 가중치가 최소가 되는 사이클이 없는 무방향 그래프이다.

 

작동 원리는 다음과 같다.

1. 간선을 가중치를 기준으로 오름차순 정렬

2. 가중 가중치가 적은 간선을 선택

3. 부모가 이어져있지 않다면 각 간선을 병합 (사이클이 형성된다면 병합 x)

4. 이어서 간선을 체크하면서 병합

 

3번에서 Union Find 알고리즘을 통해서 각 간선의 부모를 탐색하여 같은지 아닌지를 체크하여 같은 집합에 속해있는지를 확인한다.

만약 부모가 같은데 병합을 진행한다면 사이클이 형성되어 최소 신장 트리의 조건을 만족하지 않게 된다.