백준 1197 최소 스패닝 트리 c++ (MST)

문제 출처 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

문제

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

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

입력

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다.

그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 트리의 가중치가 -2,147,483,648보다 크거나 같고, 2,147,483,647보다 작거나 같은 데이터만 입력으로 주어진다.

출력

첫째 줄에 최소 스패닝 트리의 가중치를 출력한다.

알고리즘 분류

• 그래프 이론
• 최소 스패닝 트리    

풀이

그래프 알고리즘 중, 크루스칼/프림 알고리즘을 사용하는 문제이다.

나는 크리스칼 알고리즘을 이용하여 구현하였다.

각 노드의 부모 노드를 저장할 parent[10001]배열을 선언하고,

각 노드의 부모 노드는 본인 노드로 초기화한다.

 

간선들을 저장한 vt는 간선의 가중치를 기준으로 오름차순 정렬한다.

 

getParent함수는 재귀함수로, 해당 노드의 부모 노드를 찾는 함수다.

unionParent함수는 간선에 해당하는 두 개의 노드를 이어서 작은 부모 노드의 값으로 초기화한다.

findParent함수는 노드 a와 노드 b가 이어져 있는지, 즉 a와 b의 부모 노드가 같은지 확인한다.

 

최소 스패닝 트리는 모든 정점을 연결하면서, 가중치의 합이 최소여야하기 때문에 그래프에 사이클이 존재하면 안 된다.

 

1	2	3	4
1	2	2	4

2번과 3번 노드를 이으면, 그래프는 이런 형태일 것이다.

여기서 2번과 1번 노드를 이으면,

1	2	3	4
1	1	2	4

이런 형태이고, 3번과 1번을 이으려고 했더니

3번의 부모 노드는 1이고, 1번의 부모 노드도 1이기 때문에 3번과 1번은 같은 그래프에 속하기 때문에

이으면 사이클이 생겨버린다.

따라서 두 노드가 같은 그래프가 아닌 경우만(사이클이 생기지 않는 경우) 두 노드를 잇고, 
가중치를 더한다.

코드

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

using namespace std;
int v, e;
int parent[10001];

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

void unionParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

bool findParent(int a, int b) {
    a = getParent(a);
    b = getParent(b);
    if (a == b) return 1;
    else return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    for (int i = 1; i <= v; i++) {
        parent[i] = i;
    }

    for (int i = 0; i<vt.size();i++) {
        if (!findParent(vt[i].second.first, vt[i].second.second)) {
            answer += vt[i].first;
            unionParent(vt[i].second.first, vt[i].second.second);
        }

    }
    cout << answer;

    return 0;
}