[BOJ] 1197 : 최소 스패닝 트리 (C++)

📖 백준 1197번 : https://www.acmicpc.net/problem/1197

조건

시간 제한	메모리 제한
1 초	128 MB

문제

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

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

입력

첫째 줄에 정점의 개수 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

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

---

풀이

 최소 신장 트리를 구하는 잘 알려진 문제이다. 최소 신장 트리를 만드는 대표적인 알고리즘으로 크루스칼, 프림 알고리즘이 있다. 나는 크루스칼 알고리즘을 사용해서 최소 신장 트리의 가중치를 계산했다. 크루스칼 알고리즘은 가장 가중치가 작은 간선을 반복해서 선택하는 것이 첫번째이다. 선택하는 도중 사이클이 발생하지 않도록 유니온-파인드 알고리즘을 사용해서 간선을 선택한다. 노드 - 1개 만큼의 간선이 선택되었다면 최소 신장트리가 만들어 졌음이 보장된다. 이 때의 가중치의 합을 출력하면 끝이다.

코드

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

using namespace std;

int parent[100001];
int sz[100001];
struct Edge {
    int u, v;
    long long int w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};
vector<Edge> graph;

int Find(int x) {
    if (x == parent[x]) return x;
    return parent[x] = Find(parent[x]);//경로 압축
}

void Union(int x, int y) {
    x = Find(x);
    y = Find(y);

    if (x == y) return;

    if (sz[x] < sz[y]) swap(x, y);
    sz[x] += sz[y];
    sz[y] = 0;
    parent[y] = x;
}

bool isUnion(int x, int y) {
    return Find(x) == Find(y);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int a, b, w;
    int v, e;
    cin >> v >> e;

    for (int i = 0; i < e; i++) {
        cin >> a >> b >> w;
        graph.push_back({ a,b,w });
    }

    for (int i = 0; i <= v; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
    sort(graph.begin(), graph.end());

    long long int sum = 0;
    int cnt = 0;
    for (int i = 0; i < graph.size(); i++) {
        if (cnt == v - 1) break;
        if (!isUnion(graph[i].u, graph[i].v)) {
            cnt++;
            sum += graph[i].w;
            Union(graph[i].u, graph[i].v);
        }
    }
    cout << sum;

    return 0;
}