[백준 16202] MST 게임

문제 풀이

 

문제를 요약하면 다음과 같습니다.

 

MST 비용 = MST를 이루고 있는 가중치의 합

각 턴의 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거합니다.

어떤 턴에서는 MST를 만들 수 없다면, 그 턴의 점수는 0점으로 처리합니다.

같은 간선이 여러 번 주어지는 경우는 없습니다.

 

정리하면 매 턴마다 MST를 구성했을 때, MST를 만들지 못한다면? 0으로 처리하고,

MST를 구성했다면 가중치들의 합을 리턴하는 방식으로 문제를 해결해야 합니다.

 

MST를 만들 수 없다는 뜻은 무엇일까요?

문제에서도 나와있듯이 [노드의 개수 != 간선의 개수 + 1] 이여야 합니다.

만약에 위의 조건을 만족했다면 우리는 MST를 만들었다는 뜻이 되기 때문입니다.

 

따라서 매턴마다 MST를 구성하고, MST 완성을 했다면 가중치들의 합을 출력하고,

간선들 중에서 가장 가중치가 작은 간선 하나를 제거하는 것은 쉽습니다.

기존에 가중치들을 오름차순으로 정렬했기 때문에 가장 앞쪽에 있는 간선이 제일 작은 가중치이기 때문이죠.

따라서 앞에 있는 가중치를 제거하고 다시 MST를 구상하면서 턴을 반복하면 됩니다. 

 

소스 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX = 1001;
vector<pair<int, pair<int, int> > > edges;
int parent[MAX];
int N, M, K;

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

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

void input()
{
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		edges.push_back({ i + 1,{a, b} });
	}

	sort(edges.begin(), edges.end());
}

void kruskal()
{
	for (int i = 1; i <= N; i++) parent[i] = i;

	int sz = static_cast<int>(edges.size());
	int totalCost = 0;
	int totalEdges = 0;
	for (int i = 0; i < sz; i++)
	{
		int cost = edges[i].first;
		int a = edges[i].second.first;
		int b = edges[i].second.second;
		if (findParent(a) != findParent(b))
		{
			unionParent(a, b);
			totalCost += cost;
			totalEdges++;
		}
	}

	if (totalEdges + 1 == N)
		cout << totalCost << ' ';
	else
		cout << "0 ";

	// 가중치가 작은 간선을 제거
	edges.erase(edges.begin());
}

void solve()
{
	input();
	while (K--)
	{
		kruskal();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
	return 0;
}