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

문제

N개의 정점과 M개의 양방향간선으로 이루어진 단순 그래프 G가 있다. 단순 그래프란, self-loop 간선(한 정점에서 자기 자신을 이어주는 간선)이 없고, 임의의 두 정점 사이 최대 한 개의 간선이 있는 그래프를 말한다. 단순 그래프의 스패닝 트리(Spanning Tree)는 다음 조건을 만족하는 간선의 집합이다.

1. 스패닝 트리를 구성하는 간선의 개수는 N-1개이다.
2. 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다.

스패닝 트리 중에서 간선의 가중치의 합이 최소인 것을 최소 스패닝 트리(Minimum Spanning Tree, MST)라고 부른다.

이제 그래프에서 MST 게임을 하려고 한다.

• MST 게임은 그래프에서 간선을 하나씩 제거하면서 MST의 비용을 구하는 게임이다. MST의 비용이란 MST를 이루고 있는 가중치의 합을 의미한다. 각 턴의 점수는 해당 턴에서 찾은 MST의 비용이 된다.
• 이 과정은 K턴에 걸쳐서 진행되며, 첫 턴에는 입력으로 주어진 그래프의 MST 비용을 구해야 한다.
• 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다.
• 한 번 제거된 간선은 이후의 턴에서 사용할 수 없다.
• 어떤 턴에서 MST를 만들 수 없다면, 그 턴의 점수는 0이다. 당연히 이후 모든 턴의 점수도 0점이다. 첫 턴에 MST를 만들 수 없는 경우도 있다.

양방향 간선으로 이루어진 단순 그래프와 K가 주어졌을 때, 각 턴의 점수가 몇 점인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 그래프 정점의 개수 N, 그래프 간선의 개수 M, 턴의 수 K가 주어진다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ min(10,000, N×(N-1)/2), 1 < K ≤ 100)

그 후 M개의 줄에 간선의 정보가 주어진다. 간선의 정보는 간선을 연결하는 두 정점의 번호 x, y로 이루어져 있다. 같은 간선이 여러 번 주어지는 경우는 없다. 간선의 가중치는 주어지는 순서대로 1, 2, ..., M이다.

정점의 번호는 1부터 N까지로 이루어져 있다.

출력

한 줄에 공백으로 구분하여 K개의 정수를 출력해야 한다. K개의 정수는 각 턴에 얻는 점수를 나타낸다.

예제 입출력

• 예제 입력 1

6 6 2
1 2
2 3
1 3
4 5
5 6
4 6

• 예제 출력 1

0 0

• 예제 입력 2

6 7 3
2 4
1 2
4 6
1 3
2 3
4 5
5 6

• 예제 출력 2

16 0 0

• 예제 입력 3

4 5 4
3 4
1 3
1 4
1 2
2 4

• 예제 출력 3

7 9 0 0

• 예제 입력 4

5 7 4
1 2
2 3
3 4
4 5
1 5
1 4
1 3

• 예제 출력 4

10 14 0 0

• 예제 입력 5

6 9 6
1 2
2 3
3 4
4 5
5 6
1 6
1 4
2 5
3 6

• 예제 출력 5

15 20 26 32 35 0

Solution

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 1001
using namespace std;

int Parent[MAX];

int getParent(int num){
    if(num == Parent[num]) return num;
    return Parent[num] = getParent(Parent[num]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a != b) Parent[a] = b;
}

bool findParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    else return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, K; cin >> N >> M >> K;
    int idx = 0;
    vector<pair<int, pair<int, int>>> edge;
    for(int i = 1; i <= M; i++){
        int src, dst; cin >> src >> dst;
        edge.push_back({i, {src, dst}});
    }
    bool check = false;
    while(K--){
        if(check){
            cout << "0 ";
            continue;
        }
        int count = 0, answer = 0;
        for(int i = 0; i <= N; i++) Parent[i] = i;
        for(int i = idx; i < edge.size(); i++){
            int cost = edge[i].first;
            int src = edge[i].second.first;
            int dst = edge[i].second.second;
            if(!findParent(src, dst)){
                unionParent(src, dst);
                answer += cost;
                count++;
            }
        }
        if(count == N - 1) cout << answer << " ";
        else {
            check = true;
            cout << "0 ";
        }
        idx++;
    }
}

간단하다. 크루스칼을 K번 하는 문제다.
중요한 건 가중치 그 자체는 이미 정해져있다는 것이다. 입력받는 순서대로다. 그렇기에 데이터를 굳이 매번 정렬을 하거나 할 필요는 없다. 매 사이클마다 가장 가중치가 작은 간선을 날리고 MST가 가능한 지 확인해주기만 하면 된다.

bool check = false;
while(K--){
    if(check){
        cout << "0 ";
        continue;
    }
    int count = 0, answer = 0;
    for(int i = 0; i <= N; i++) Parent[i] = i;
    for(int i = idx; i < edge.size(); i++){
        int cost = edge[i].first;
        int src = edge[i].second.first;
        int dst = edge[i].second.second;
        if(!findParent(src, dst)){
            unionParent(src, dst);
            answer += cost;
            count++;
        }
    }
    if(count == N - 1) cout << answer << " ";
    else {
        check = true;
        cout << "0 ";
    }
    idx++;
}

크루스칼 알고리즘 결과가 만약 MST가 생성되지 않는다면 다음 사이클 부터는 무조건 0 처리 하기 위해 boolean 데이터를 하나 정해뒀다. 한번이라도 MST 가 구해지지 않았다면 다음 모든 사이클을 0 처리 하기 위해서다.

MST가 구해졌는 지 확인하는 방법은 간단하다. 모든 노드들이 다 연결되어있는 지를 확인하는 것이다. unionParent 함수가 실행 된 횟수가 N-1이냐를 확인하면 된다.