[백준 1922번] [MST / Union-Find] 네트워크 연결

전형적인 Minimum cost Spanning Tree (최소 스패닝 트리) 문제이다.

 

모든 지점이 연결되어야 한다는 측면에서 스패닝 트리이고, 최소 비용을 구하는 상황이므로 최소 스패닝 트리이다.

 

최소 스패닝 트리는 Prim 알고리즘과 Kruskal 알고리즘이 있는데, 일반적으로는 Kruskal 알고리즘을 많이 사용한다.

 

해당 알고리즘을 요약하자면 다음과 같다.

 

1. Cost 순서대로 정렬한다.

2. Cost 순으로 방문하되, 연결된 집단끼리는 하나의 집단을 형성한다.
(만약 동일한 집단끼리 연결되는 경우에는 해당 경로를 제외해주면 된다.)

3. 결과적으로 모든 노드들이 하나의 집합을 형성하게 될 때 Minimum cost를 만족하게 된다.

이때, 집합에 속하냐 속하지 않냐를 기준으로 구현하는 양상을 띄고 있으므로 Union-Find 자료구조를 활용하고 있다.

코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;
int visited[1001];

struct DisjointSet{
    vector<int> parent, rank;
    DisjointSet(int n) : parent(n), rank(n, 1){
        for(int i = 0; i < n; i++){
            parent[i] = i;
        }
    }

    int find(int n){
        if(parent[n] == n) return n;
        else{
            return parent[n] = find(parent[n]);
        }
    }

    void merge(int n, int m){
        n = find(n); m = find(m);
        if(n == m) return;
        if(rank[n] < rank[m]) swap(n, m);
        parent[m] = n;
        if(rank[n] == rank[m]) rank[n]++;
        return;
    }
};

struct path{
    int start;
    int end;
    int price;
    path(int temp1, int temp2, int temp3) : start(temp1), end(temp2), price(temp3) 
    {}
};

struct compare{
    bool operator()(const path &data1, const path &data2){
        if(data1.price == data2.price){
            return data1.start > data2.start;
        }
        else return data1.price > data2.price;
    }
};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    memset(visited, 0, sizeof(visited)); // 방문 0으로 초기화
    int N, M;
    cin >> N;
    cin >> M;

    priority_queue<path, vector<path>, compare> pq;
    DisjointSet world(N + 1);

    for(int i = 0; i < M; i++){
        int temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        pq.push(path(temp1, temp2, temp3));
    } // 길 정보 저장

    int current_price = 0;
    while(pq.size() != 0){
        if(world.find(pq.top().start) == world.find(pq.top().end)){
            pq.pop();
        }
        else{
            world.merge(pq.top().start, pq.top().end);
            current_price += pq.top().price;
            pq.pop();
        }
    }

    cout << current_price << "\n";

    return 0;
}

무난하게 통과하였다.

 

최소 스패닝 트리를 처음 배우고 푼 것 치고는 잘 푼 것 같다.