백준 1197번 - 최소 스패닝 트리

백준 1197번 - 최소 스패닝 트리

https://www.acmicpc.net/problem/1197

문제

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

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

입력

• 첫째 줄에 정점의 개수 V(1≤V≤10,000)와 간선의 개수 E(1≤E≤100,000)가 주어진다.

• 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다.

• 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다.

• C는 음수일 수도 있으며, 절대값이 1,000,000을 넘지 않는다.

출력

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

접근

• 최소 스패닝 트리(MST) 문제이다.

• Prim 알고리즘을 활용해본다.

Prim 알고리즘

• 임의의 정점을 선택하여, 나머지 정점들과의 거리를 기록한다.

  • 연결 못하는 경우 ​

• 기록된 거리중 가장 비용이 낮은 거리를 선택하고, 그 정점을 연결하여 트리를 생성한다.

• 그 정점을 기준으로 다시 나머지 정점들과의 거리를 기록하여 반복한다.

C++ Code

#include <cstdio>
#include <tuple>
#include <vector>
using namespace std;
​
const int INF = 987654321;
​
int v, e;
int a, b, w;
vector<vector<pair<int, int>>> adj;
​
int prim() {
    vector<int> cost(v + 1, INF);
    vector<int> visited(v + 1, false);
    int ret = 0;
    cost[1] = 0;
​
    for (int iter = 0; iter < v; iter++) {
        int a = 0;
        for (int b = 1; b <= v; b++) {
            if (!visited[b] && cost[a] > cost[b]) {
                a = b;
            }
        }
​
        ret += cost[a];
        visited[a] = true;
​
        for (int i = 0; i < adj[a].size(); i++) {
            b = adj[a][i].first;
            w = adj[a][i].second;
            
            if (cost[b] > w) {
                cost[b] = w;
            }
        }
    }
​
    return ret;
}
​
int main(void) {
    scanf("%d %d", &v, &e);
    adj.resize(v + 1);
​
    for (int i = 0; i < e; i++) {
        scanf("%d %d %d", &a, &b, &w);
        adj[a].push_back({ b, w });
        adj[b].push_back({ a, w });
    }
​
    printf("%d\n", prim());
​
    return 0;
}