[백준] 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보다 작거나 같은 데이터만 입력으로 주어진다.

출력

---

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

---

풀이)

MST에 대한 설명링크 https://comyoung.tistory.com/121?category=842225 

Prim 알고리즘과 Kruskal 알고리즘 둘 다 구현해보았다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int V, E, A, B, C;
//Prim
vector <pair<int,int>> adj[10001];//{가중치, 연결 정점}
bool visited[10001]; 
 
//Kruskal
struct Edge {
    int s, e, cost;
    bool operator < (const Edge &t) {
        return cost < t.cost;
    }
};
vector <Edge> e;
int parent[10001];
int s[10001];
 
int Prim(int vertex) {
    int result = 0;
    priority_queue <pair<int, int>> qu;//{간선가중치, 연결정점}
    qu.push({ 0,1 });
    
    for (int i = 1; i <= V; i++) {//총 V번 진행
        int here, dist, min_dist = 999999;
        while (!qu.empty())
        {
            here = qu.top().second;
            dist = -qu.top().first;
            qu.pop();
            if (!visited[here]) {
                min_dist = dist;
                break;
            }
        }
        result += min_dist;
        visited[here] = true;
        for (int i = 0; i < adj[here].size(); i++) {
            //간선 가중치에 -붙이는 이유는 => PQ가 내림차순이 기본으로 되어 있기 때문이다
            qu.push({ -adj[here][i].first,adj[here][i].second });
        }
    }
    return result;
}
 
int Find(int a) {
    if (a == parent[a]) return a;
    return parent[a] = Find(parent[a]);
}
 
int Kruskal() {
    for (int i = 1; i <= V; i++) {
        parent[i] = i;
        s[i] = 1;
    }
 
    sort(e.begin(), e.end()); //간선들을 오름차순으로 정렬
    int result = 0;
    for (int i = 0; i < e.size(); i++) {
        int v1 = Find(e[i].s);
        int v2 = Find(e[i].e);
        if (v1 == v2) continue; // 이미 같은 집합이면 pass
        if (s[v1] < s[v2]) swap(v1, v2);
        parent[v2] = v1;
        s[v1] += s[v2];
        result += e[i].cost;
    }
    return result;
}
 
int main() {
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++) {
        scanf("%d %d %d", &A, &B, &C);
        adj[A].push_back({ C,B }); //Prim에 이용하기 위해
        adj[B].push_back({ C,A });
 
        e.push_back({ A,B,C }); //Kruskal에 이용하기 위해
    }
    //printf("%d", Prim(1));
    printf("%d", Kruskal());
    return 0;
 
}