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

문제

도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.)

그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다.

입력

첫째 줄에 컴퓨터의 수 N (1 ≤ N ≤ 1000)가 주어진다.

둘째 줄에는 연결할 수 있는 선의 수 M (1 ≤ M ≤ 100,000)가 주어진다.

셋째 줄부터 M+2번째 줄까지 총 M개의 줄에 각 컴퓨터를 연결하는데 드는 비용이 주어진다. 이 비용의 정보는 세 개의 정수로 주어지는데, 만약에 a b c 가 주어져 있다고 하면 a컴퓨터와 b컴퓨터를 연결하는데 비용이 c (1 ≤ c ≤ 10,000) 만큼 든다는 것을 의미한다. a와 b는 같을 수도 있다.

출력

모든 컴퓨터를 연결하는데 필요한 최소비용을 첫째 줄에 출력한다.

예제 입출력

• 예제 입력 1

6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
3 5 11
4 5 3
4 6 8
5 6 8

• 예제 출력 1

23

Solution

이번 포스팅에서는 Prim Algorithm을 활용해보겠다.

#include <iostream>
#include <vector>
#include <queue>
#define MAX 100001
using namespace std;

int N,M;
vector<pair<int, int>> edge[MAX];
bool visited[MAX];

int prim(){
    priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int result = 0;
    pq.push({0, 1});
    for(int i = 1; i <= N; i++){
        while(!pq.empty() && visited[pq.top().second]){
            pq.pop();
        }
        int next = pq.top().second;
        int minCost = pq.top().first;
        visited[next] = true;
        result += minCost;
        for(auto i : edge[next]){
            pq.push({i.second, i.first});
        }
    }
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge[src].push_back({dst, cost});
        edge[dst].push_back({src, cost});
    }

    cout << prim() << '\n';
}

Prim Algorithm은 '최소 스패닝 트리' 즉 MST를 찾는 문제다. 크루스칼 알고리즘과 차이가 있다면 효율성에 있어서 차이가 있다는 것.
알고리즘은 다음과 같다.

1. 임의의 정점을 하나 선택하여 Tree에 집어넣는다.
2. Tree 에 있는 노드와 Tree에 없는 노드 중 가중치가 최소인 간선을 찾는다.
3. 찾은 간선이 연결하는 두 노드 중 Tree에 없던 노드를 포함시킨다.
4. 모든 노드가 Tree에 포함될 때 까지 반복.

물론 코드를 보면 그 Tree라고 할만한 게 따로 있지는 않다. 애초에 MST가 뭔지 잘 생각해봐야 한다.

Minimum Spanning Tree : 최소의 비용으로 연결 된 노드의 그래프

이 문제의 조건과 동일하다. Kruskal Algorithm 또한 마찬가지다. 구현의 용이성을 위해 아까완 다르게 간선을 저장하는 vector의 형태가 좀 다르다. src, dst 두 개의 정보를 각각 따로 저장한다.

int prim(){
    priority_queue< pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    int result = 0;
    pq.push({0, 1});
    for(int i = 1; i <= N; i++){
        while(!pq.empty() && visited[pq.top().second]){
            pq.pop();
        }
        int next = pq.top().second;
        int minCost = pq.top().first;
        visited[next] = true;
        result += minCost;
        for(auto i : edge[next]){
            pq.push({i.second, i.first});
        }
    }
    return result;
}

가중치가 최소인 점을 찾아야 하고, 임의의 정점을 선택해야 하므로 우선순위 큐를 활용했다. 우선 시작으로 0의 비용으로 1부터 탐색을 시작한다.

for(int i = 1; i <= N; i++){
    while(!pq.empty() && visited[pq.top().second]){
        pq.pop();
    }
    int next = pq.top().second;
    int minCost = pq.top().first;
    visited[next] = true;
    result += minCost;
    for(auto i : edge[next]){
        pq.push({i.second, i.first});
    }
}

우선 visited 상에서 방문했던 이력이 있는 노드들을 모두 pop 해 버린다. 그리고 남은 노드의 데이터를 통해 다음에 탐색할 노드, 최소비용을 갱신한다. 최소비용은 result 변수에 더한다. 그리고 해당 노드를 방문 처리 후 그 노드가 방문할 수 있는 모든 노드를 우선순위 큐에 집어넣는다.

처음에 1번 노드를 입력했을 때는 방문했던 이력이 아무것도 없으니 top은 그대로일 것이다. 그럼 자연스래 1번 노드부터 방문처리 후 방문 할 수 있는 모든 노드들을 입력할것이다. 이런 식으로 기존에 방문했던 노드를 제거하고, 우선순위 큐이고 minheap 형태니까 최소한의 비용을 쓰는 노드가 top에 위치 할 것이다. 노드 갯수만큼 이 작업을 반복한다.

우선순위 큐를 활용할 줄 안다면 이 문제 또한 어렵지 않게 풀 수 있을 것이다. 지금까지 Kruskal, Prim 두 가지 알고리즘을 통해 이 문제를 풀어보았다.