[BOJ 1197 / C++] 최소 스패닝 트리 (최소 신장 트리)

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

 

> 방법 1. 크루스칼 알고리즘(Kruskal Algorithm)

1-1. 코드

#include <bits/stdc++.h>
using namespace std;

int find(vector<int>& p, int x) {
    if (p[x] < 0) return x;
    return p[x] = find(p, p[x]);
}

bool uni(vector<int>& p, int u, int v) {
    u = find(p, u);
    v = find(p, v);

    if (u == v) return false;
    p[v] = u;
    return true;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int v, e;
    cin >> v >> e;
    
    vector<tuple<int, int, int>> edge(e); // {비용, 정점1, 정점2}

    for (int i = 0; i < e; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;
        edge[i] = {cost, a, b};
    }
    sort(edge.begin(), edge.end());

    int cnt = 0;
    int ans = 0;
    vector<int> p(v+1, -1);
    for (int i = 0; i < e; i++) {
        int a, b, cost;
        tie(cost, a, b) = edge[i];
        if (!uni(p, a, b)) continue;
        ans += cost;
        cnt++;
        if (cnt == v-1) break;
    }
    cout << ans;
}

 

 

1-2. 시간복잡도

크루스칼 알고리즘의 시간복잡도는 O(elge)이다. 

 

 

1-3. 분석

{비용, 정점1, 정점2}를 vector로 저장하고, 오름차순 정렬을 해놓는다. 이후 union find를 하면서 최소신장트리에 포함시키고 트리 정보는 parent 배열에 담는다.

 

 

> 방법 2. 프림 알고리즘 (Prim Algorithm)

2-1. 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    int v, e;
    cin >> v >> e;
    
    vector<vector<pair<int, int>>> adj(v+1); // {비용, 정점} 

    for (int i = 0; i < e; i++) {
        int a, b, cost;
        cin >> a >> b >> cost;

        adj[a].push_back({cost, b});
        adj[b].push_back({cost, a});
    }

    // tuple<int, int, int> : {비용, 정점1, 정점2}
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>> > pq;
    vector<bool> chk(v+1);

    chk[1] = true;
    for (auto nxt : adj[1]) {
        pq.push({nxt.first, 1, nxt.second});
    }

    int ans = 0;
    int cnt = 0;
    while (cnt < v-1) {
        int cost, a, b;
        tie(cost, a, b) = pq.top(); pq.pop();
        if (chk[b]) continue;
        ans += cost;
        chk[b] = true;
        cnt++;
        for (auto nxt : adj[b]) {
            if (!chk[nxt.second]) pq.push({nxt.first, b, nxt.second});
        }
    }
    cout << ans;
}

 

 

2-2. 시간복잡도

프림 알고리즘의 시간복잡도는 O(elge)이다.

 

 

2-3. 분석

우선순위 큐와 check 배열을 통해서 비용이 적은 순서대로 신장트리에 추가시켜서 최소비용을 구해낸다.