[백준] 16202번 : MST 게임

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 최소 신장 트리(MST) 문제로, 한 그래프에서 MST를 구한 뒤 가중치가 가장 작은 간선을 하나씩 제거해야하므로 가중치의 오름차순으로 간선들을 정렬하여 가장 앞에 있는 원소부터 하나씩 제거해나가며 풀면 된다. 이 문제에서는 MST를 구하기 위해 크루스칼 알고리즘을 사용했다.

1) 간선들의 정보를 저장하는 벡터 edges를 만들어 각 간선들의 (가중치, 노드 a, 노드 b)를 저장한다.

2) edges를 가중치의 오름차순으로 정렬한다.

3) 아래 과정을 입력받은 게임의 턴 수만큼 반복한다.

• 사이클 테이블에 각 노드(섬)들의 부모를 자기 자신으로 지정한다.
• edges에 저장된 각 간선들에 대해서 크루스칼 알고리즘을 적용한다.
  • 현재 순서 간선의 노드 a, 노드 b를 확인해 같은 그래프에 있지 않으면(find) 두 노드를 이어 부모를 합치고(union), answer에 간선의 가중치를 누적시킨다.
  • 이 때, 지금까지 이어진 간선의 개수를 누적시키기 위해 count에 1을 더한다.
• 위 과정을 진행한 뒤에
  • count가 정확히 (정점 개수 - 1)개이면 answer를 출력
  • 아니라면 MST가 성립 불가능하므로 0을 출력
• 정렬된 간선들의 가장 첫 번째 (가중치가 가장 작은) 간선을 제거 한다.

🖥️ 풀이 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;
typedef tuple<int, int, int> tiii;

int parent[1001];

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

void unionParent(int a, int b)
{
	a = getParent(a);
	b = getParent(b);

	if (a < b)
		parent[a] = b;
	else
		parent[b] = a;
}

int findParent(int a, int b)
{
	a = getParent(a);
	b = getParent(b);

	return (a == b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(); cout.tie();

	int n, m, k;
	cin >> n >> m >> k;

	vector<tiii> edges;
	for (int i = 0; i < m; i++)
	{
		int a, b, c = i + 1;
		cin >> a >> b;
		edges.push_back(tiii(c, a, b));
	}
	sort(edges.begin(), edges.end());

	for (int i = 0; i < k; i++)
	{
		int answer = 0, count = 0;
		for (int i = 0; i <= n; i++)
			parent[i] = i;

		for (int i = 0; i < edges.size(); i++)
		{
			int curA = get<1>(edges[i]);
			int curB = get<2>(edges[i]);

			if (!findParent(curA, curB))
			{
				unionParent(curA, curB);
				answer += get<0>(edges[i]);
				count++;	// 간선 이어질 때마다 count 증가
			}
		}

		// 간선의 개수가 정확히 (정점 개수 - 1)이 아니면 MST 성립 불가능
		if(count == n - 1)
			cout << answer << ' ';
		else
			cout << 0 << ' ';

		// 정렬된 간선들의 가장 첫 번째 (가중치가 가장 작은 간선) 제거
		edges.assign(edges.begin() + 1, edges.end());
	}
}