[BOJ/Gold 4] 백준 16202 MST 게임(C++)

문제 링크

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

16202번: MST 게임

 

문제

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

첫 턴에 MST를 찾을 수 없어서 모든 턴의 점수가 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

힌트

첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다.

두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있는 간선을 이용해 MST를 찾아야 한다. 하지만, (2, 4)를 없앤 후 MST가 존재하지 않기 때문에, 두 번째 턴과 그 이후 모든 턴의 점수는 0이 된다.

알고리즘 분류

• 크루스칼 알고리즘

풀이

주어진 정보로 총 K번 최소 스패닝 트리의 가중치를 구한다.

그러기 위해서는 K번마다 최소 스패닝 트리의 가중치를 구하기 이전에, 각 정점의 Parent를 자기 자신으로 초기화시켜준다. 그리고 최소 스패닝 트리를 구성하면서, 가중치가 가장 낮은 간선을 제외시킨다.

모든 정점의 Parent가 1번 정점이라면, 최소 스패닝 트리가 만들어졌다는 것을 의미한다. 따라서 최소 스패닝 트리의 가중치를 출력한다.

어떤 정점의 Parent가 1번 정점이 아니라면, 최소 스패닝 트리를 만들지 못 했다는 것을 의미하므로, Flag를 false로 초기화시키고 0을 출력한다. 

Flag가 false라면, 남은 횟수 동안에는 최소 스패닝 트리를 만들지 못 한다는 뜻이므로 0을 출력한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
struct INFO {
	int Start, End, Cost;
	bool isAble;
};

int N, M, K;
vector<INFO> Edge;
int Parent[MAX];
bool Flag = true;
int answer;

void Init() {
	for (int i = 1; i <= N; i++) {
		Parent[i] = i;
	}
	answer = 0;
}

int Find(int X) {
	if (Parent[X] == X) {
		return X;
	}
	return Parent[X] = Find(Parent[X]);
}

void Union(int X, int Y) {
	int PX = Find(X);
	int PY = Find(Y);
	if (PX < PY) {
		Parent[PY] = PX;
	}
	else {
		Parent[PX] = PY;
	}
}

bool Comp(INFO A, INFO B) {
	return (A.Cost < B.Cost);
}

bool isConnected() {
	for (int i = 2; i <= N; i++) {
		if (Find(i) != Find(1)) {
			return false;
		}
	}
	return true;
}

void Input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= M; i++) {
		int X, Y;
		cin >> X >> Y;
		Edge.push_back({ X,Y,i,true });
	}
	sort(Edge.begin(), Edge.end(), Comp);
}

void Settings() {
	int IDX = 0;
	int minCost = INF;
	for (int i = 0; i < Edge.size(); i++) {
		int C = Edge[i].Cost;
		int X = Edge[i].Start;
		int Y = Edge[i].End;
		bool isAble = Edge[i].isAble;
		if ((Find(X) != Find(Y)) && isAble) {
			if (minCost > C) {
				minCost = C;
				IDX = i;
			}
			Union(X, Y);
			answer += C;
		}
	}
	Edge[IDX].isAble = false;
}

void Find_Answer() {
	while (K--) {
		Init();
		if (!Flag) {
			cout << 0 << " ";
			continue;
		}
		Settings();
		if (isConnected()) {
			cout << answer << " ";
		}
		else {
			Flag = false;
			cout << 0 << " ";
		}
	};
	cout << "\n";
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}