[백준 16202 C++][G4] MST 게임

⭐️ 난이도

 

Gold 4

---

⭐️ 문제

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

16202번: MST 게임

 

 

---

⭐️ Idea flow

 

이 문제는 이름에서부터 알 수 있듯이 MST(Minimum Spanning Tree) 알고리즘을 이용해서 풀어야하는 문제였다.

처음에는 이 문제를 prim 알고리즘으로 풀어보려고 했는데, "MST를 이루는 간선 중 가중치가 제일 적은 간선"을 제거하기 위한 필요한 정보가 많다고 느꼈다.

 

반면 Kruskal 알고리즘은 애초에 간선을 가중치 순으로 정렬을 하기 때문에 가중치가 제일 적은 간선을 찾기가 쉽다.

따라서 Kruskal(크루스칼)알고리즘을 사용하기로 했다.

 

이 문제에서 중요한 포인트가 두 가지가 있는데,

1. MST가 제대로 생성되었는지 확인해야 한다.

2. MST가 제대로 생성되었다면, "MST를 구성하는 간선" 중에서 가중치가 제일 적은 간선을 제거해야 한다.

3. 한 번 MST가 제대로 생성이 안됐다면, 이후에도 MST가 생성되지 않는다.

 

1번의 경우를 생각해보자.

크루스칼 알고리즘은 union-find를 사용한다. 

MST가 제대로 생성되었다는 말은 모든 노드가 연결되어 있다는 말인데, 모든 노드의 부모 노드의 값이 같으면 모든 노드가 연결되어있다고 볼 수 있다.

여기서 중요한 것은 검사를 하기 전에 모든 노드의 parent 값을 한 번 갱신해줘야 한다는 점이다.

 

2번의 경우를 생각해보자.

여기서 중요한 점은 그저 가중치가 제일 적은 간선을 제거하는 것이 아니라, "MST를 구성하는 간선"중에서 가중치가 제일 적은 간선을 제거하는 것이다.

따라서 크루스칼 알고리즘을 실행하면서 추가하는 간선의 가중치를 살펴보고 제일 적은 가중치의 인덱스를 변수에 저장한다.

이제 없앨 간선의 인덱스를 알았으니 제거만 하면 되는데, vector에서 erase를 통해 매번 요소(element)를 제거하는 것은 성능 저하를 일으킬 수 있다.

그렇다면 실질적으로 요소를 제거하는 것이 아니라, 해당 요소를 제거했다고 "표시"를 하면 어떨까?

Edge 구조체에 bool isSelected를 선언해서 제거되는 간선인 경우 isSelected = true로 바꾼다.

이후 간선을 확인할 때에는 isSelected = false인 간선만 확인하면 된다.

 

3번의 경우를 생각해보자.

이 부분을 효율성에서 생각하게 된 부분이다.

MST가 한 번 생성되지 않으면 그 이후의 경우에도 형성되지 않으므로 계속해서 MST 생성 여부를 확인할 필요가 없다.

따라서 bool flag를 선언하고 크루스칼 이후에 MST가 생성되지 않으면 flag = true로 전환해준다.

이후의 턴에서 flag가 true인 것을 확인하면 MST 알고리즘을 실행하지 않고 0을 출력해준다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_set>

#define INF 987654321;
using namespace std;

// 16202 - MST 게임
struct Edge{
    int node[2], dist;
    bool isSelected;

    Edge(int a, int b, int dist, bool isSelected){
        this->node[0] = a;
        this->node[1] = b;
        this->dist = dist;
        this->isSelected = isSelected;
    }
    bool operator < (Edge edge){
        return this->dist < edge.dist;
    }
};
int n, m, k; // 노드의 개수, 간선의 개수, 턴의 개수
int sum = 0, idx = 0;
vector<int> parent;
vector<Edge> graph;


void input(){
    cin >> n >> m >> k;
    parent.assign(n + 1, 0);

    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        graph.emplace_back(a, b, i, false);
    }
}

void initParent(){
    for(int i = 1; i <= n; i++){
        parent[i] = i;
    }
}

int getParent(int x){
    if(x == parent[x])  return x;
    return parent[x] = getParent(parent[x]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a < b)   parent[b] = a;
    else    parent[a] = b;
}

bool isParentSame(int a, int b){
    a = getParent(a);
    b = getParent(b);
    return a == b;
}

void kruskal(){
    int min_dist = INF;
    sum = 0;

    for(int i = 0; i < graph.size(); i++){
        if(!isParentSame(graph[i].node[0], graph[i].node[1]) && !graph[i].isSelected){
            if(min_dist > graph[i].dist){
                min_dist = graph[i].dist;
                idx = i;
            }
            sum += graph[i].dist;
            unionParent(graph[i].node[0], graph[i].node[1]);
        }
    }

    graph[idx].isSelected = true;
}

bool isAllConnected(){
    // 모든 정점의 parent가 제대로 갱신이 안되어있을수도 있으니 갱신을 한 차례 해준다.
    for(int i = 1; i <= n; i++){
        getParent(i);
    }

    int base = parent[1];
    for(int i = 2; i <= n; i++){
        if(base != parent[i])   return false;
    }
    return true;
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    input();
    sort(graph.begin(), graph.end());

    bool flag = false;
    while(k--){
        // 1. MST가 제대로 생성되었는지의 여부 확인 필요 : parent의 값이 모두 같아야 한다
        // 2. MST가 만들어졌다면 MST를 구성하는 간선 중 가중치가 제일 작은 간선 삭제 필요 : kruskal 알고리즘
        if(!flag){
            initParent();
            kruskal();

            if(isAllConnected()){
                cout << sum << " ";
            }
            else{
                flag = true;
                cout << "0 ";
            }
        }
        else{
            cout << "0 ";
        }
    }

    return 0;
}

 

---

⭐️ Feedback

 

오늘 MST를 다시 공부하고 이를 적용해보기 위해 이 문제를 선택했다.

의도하진 않았지만 이 문제를 통해서 prim 알고리즘과 kruskal의 알고리즘의 차이점을 알 수 있었다.

 

kruskal 알고리즘의 경우 간선을 선택하는 알고리즘이므로, 1) 간선의 개수가 적어서 간선 정렬에 시간이 얼마 걸리지 않는 경우, 2) 간선을 중점적으로 봐야하는 상황인 경우 사용하면 좀 더 유용하고,

 

prim 알고리즘의 경우 정점을 선택하는 알고리즘이므로, 1) 간선의 갯수가 많아서 kruskal 알고리즘의 시간이 좀 더 오래 걸리는 경우, 2) 트리 구조를 계속해서 유지해야 하는 경우에 사용하면 좀 더 유용하다.