Boj 1197 c++ 최소 스패닝 트리

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

 

그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.

최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.

 

**신장 트리란?**

그래프 상에서 모든 노드가 사이클 없이 연결된 부분 그래프

사이클이 없으므로, 정점의 개수가 v개일 때 간선은 반드시 v-1개여야 한다.

 

최소 신장 트리 --> 신장 트리 중에서 간선의 가중치의 합이 최소인 트리

 

 

각 간선의 가중치를 고려하여 신장트리를 구성할 것들을 적절히 골라주면 된다.

 

 for(int i = 0; i < E; i++){
        int a, b, c;

        if(cnt == V-1)
            break;

        c = v[i].first;
        a = v[i].second.first;
        b = v[i].second.second;

        if(Find(a) == Find(b))
            continue;

        Union(a, b);
        ans += c;
        cnt++;
    }

 

우선 사이클이 생기면 안된다는 조건은 분리집합을 이용하면 편하다.

두 정점의 대표 원소가 같다는 것은 두 정점이 이미 한번 연결되었다는 뜻이며, 이 두 정점을 서로 연결하는 간선을 추가할 경우, 사이클이 생기게 된다.

 

 

**사진과 같은 신장 트리에서 A와 B는 같은 조상을 공유하고 있기에 둘을 연결하는 간선을 그으면 사이클이 생긴다. **

 

 

그래프에 대한 정보를 가중치에 대하여 오름차순으로 정렬한다.

가중치가 작은 간선 부터 참조하여 사이클이 생기지 않는 조건 하에 그리디하게 간선들을 선택하는 것이다.

 

간선의 개수가 v-1개가 되는 순간에 루프를 멈추면 최소 스패닝 트리의 가중치 합을 구할 수 있다.

 

전체 코드

 

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

using namespace std;

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

int Find(int x) {
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

void Solve(int V, int E) {

    int cnt = 0, ans = 0;

    for(int i = 0; i <= V; i++) {
        parent[i] = i;
    }

    for(int i = 0; i < E; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        v.push_back({c, {a, b}});
    }
    sort(v.begin(), v.end());

    for(int i = 0; i < E; i++){
        int a, b, c;

        if(cnt == V-1)
            break;

        c = v[i].first;
        a = v[i].second.first;
        b = v[i].second.second;

        if(Find(a) == Find(b))
            continue;

        Union(a, b);
        ans += c;
        cnt++;
    }

    cout << ans;

}

int main() {

    int V, E;

    cin >> V >> E;

    parent.resize(V+1);

    Solve(V, E);
}