[백준 11085번] [MST / Union-Find] 군사 이동

사실 이 문제를 보고 가장 먼저 든 생각은 최소 스패닝 트리의 해법과 비슷하게 풀면 된다는 것이다.

특히 Kruskal 알고리즘 해법과 되게 비슷한 느낌이 들었다.

 

정확하게 이 문제는 스패닝 트리를 구하는 것이 아니다.

왜냐하면, 출발과 목적 지점을 포함하기만 하면 되지 모든 노드들을 전부 방문할 필요는 없기 때문이다.

 

하지만 Kruskal 알고리즘 기법을 활용하겠다고 마음을 먹은 이유는 다음과 같다.

 

1. 결과적으로 길이 최대가 되게끔 계속해서 만들어야 한다.

 

2. 즉 이러한 알고리즘은 사실상 최소 값들을 priority_queue에 저장하고 탐욕적으로 집합을 만드는 Kruskal 알고리즘과 매우 유사하다.

 

3. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 논리와 상당히 유사함을 인식할 수 있다.

 

다만, 이 문제에서 최소 스패닝 트리와 접근 방법이 유일하게 다른 지점은

탐욕적으로 탐색하되 수도가 하나의 집합 안으로 들어온 순간 정지시키면 된다.

 

왜냐하면, 수도끼리 연결되었음에도 불구하고 스패닝 트리를 구성하는 과정에서 너비의 손해가 발생할 수 있기 때문이다.

 

이 지점만 고려해서 코드로 구현해주면 된다.

 

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

using namespace std;
#define INF 123456789

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 node_data{
    int start;
    int end;
    int cost;
    node_data(int temp1, int temp2, int temp3) : start(temp1), end(temp2), cost(temp3)
    {}
};

struct compare{
    bool operator()(const node_data &data1, const node_data &data2){
        return data1.cost < data2.cost;
    }
};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int p, w;
    cin >> p >> w;
    int c, v;
    cin >> c >> v;

    priority_queue<node_data, vector<node_data>, compare> pq;
    DisjointSet world(p + 1);

    for(int i = 0; i < w; i++){
        int temp1, temp2, temp3;
        cin >> temp1 >> temp2 >> temp3;
        pq.push(node_data(temp1, temp2, temp3));
    }

    int min_store = INF;

    while(pq.size() != 0){
        if(world.find(c) == world.find(v)) break;
        
        if(world.find(pq.top().start) == world.find(pq.top().end)){
            pq.pop();
        }
        else{
            world.merge(pq.top().start, pq.top().end);
            min_store = min(min_store, pq.top().cost);
            pq.pop();
        }
    }

    cout << min_store << "\n";

    return 0;
}