[백준 - 1197] 최소 스패닝 트리 - C++

분류: 최소 신장 트리(MST), 프림의 알고리즘, 크루스칼의 알고리즘, union-find /

 

문제

문제 링크

문제 설명

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

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

입력

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

출력

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

 

풀이

- Prim's Algorithm

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct xw {int x, w;};
int V, E;
bool vis[10001];
vector<xw> adj[10001];

bool cmp(xw &a, xw &b) {return a.w > b.w;}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> V >> E;
    while(E--) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    priority_queue<xw, vector<xw>, decltype(&cmp)> pq(cmp);
    pq.push({1, 0});

    int len = 0, cnt = 0;
    while(!pq.empty()) {
        const auto [x, w] = pq.top(); pq.pop();
        if(vis[x]) continue;
        vis[x] = true;
        len += w;
        if(++cnt == V) break;
        for(const auto [nx, nw]:adj[x])
            if(not vis[nx]) 
                pq.push({nx, nw});
    }
    cout << len;
}

확정된 정점 집합에 연결된 간선 중 비용이 가장 낮은 간선을 MST에 포함하고 정점을 확정(`vis[] = true`)

다익스트라 알고리즘과 비슷해 보이지만 다익스트라는 시작점으로 부터 가장 가까운 정점 선택

프림의 알고리즘은 확정된 정점 집합을 하나의 정점으로 보는 다익스트라로 생각할 수 있음.

 

Python

import sys, heapq
readline = sys.stdin.readline

V, E = map(int, readline().split())
adj = [[] for _ in range(V + 1)]
vis = [False] * (V + 1)

for _ in range(E):
    a, b, c = map(int, readline().split())
    adj[a].append((c, b))
    adj[b].append((c, a))

ans = cnt = 0
heap = [(0, 1)]

while cnt < V:
    w, x = heapq.heappop(heap)
    if vis[x]:
        continue
    
    vis[x] = True
    cnt += 1
    ans += w
    for pair in adj[x]:
        if not vis[pair[1]]:
            heapq.heappush(heap, pair)

print(ans)

 

- Kruskal's Algorithm

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int V, E;
int parent[10001];
pair<int, pair<int, int>> edges[100000];

inline int fnd(int x) {
    return parent[x] ? (parent[x] = fnd(parent[x])) : x;
}
inline void uni(int a, int b) {
    parent[fnd(b)] = fnd(a);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> V >> E;
    for(int i=0; i<E; i++) {
        int a, b, c; cin >> a >> b >> c;
        edges[i] = {c, {a, b}};
    }
    sort(edges, edges+E);

    int ans = 0;
    for(int i=0; i<E; i++) {
        const int &cost = edges[i].first;
        const auto &[a, b] = edges[i].second;
        if(fnd(a) == fnd(b)) continue;
        uni(a, b);
        ans += cost;
    }
    cout << ans;
}

• 그리디하게 가장 비용이 작은 간선을 선택
• 선택된 간선을 MST에 포함했을 때 사이클을 만드는지 확인
  • 사이클을 만든 다면 다음 간선 확인
  • 사이클을 만들지 않는다면 MST에 포함

union-find로 사이클 확인.

선택된 간선의 두 정점의 루트가 같다면 사이클

`fnd()`는 루트를 찾는 함수. 루트를 찾으며 지나는 경로의 모든 부모 정점의 루트를 최종 루트로 변경

`uni()`는 각 정점의 루트를 찾아 루트끼리 연결하는 함수. 루트끼리 연결하는 것이기 때문에 부모-자식 방형을 상관 없음

 

Python

import sys, heapq
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def find(x):
    if parents[x] == x:
        return x
    parents[x] = find(parents[x])
    return parents[x]

V, E = map(int, readline().split())
edges = []

for _ in range(E):
    a, b, c = map(int, readline().split())
    heapq.heappush(edges, (c, (a, b)))

ans = 0
parents = [x for x in range(V + 1)]

while edges:
    w, (x, y) = heapq.heappop(edges)
    X, Y = find(x), find(y)
    if X != Y:
        parents[X] = Y
        ans += w

print(ans)