취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 4792번 문제인 레드 블루 스패닝 트리이다.
문제는 아래 링크를 확인하자.

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

입력으로 연결그래프가 주어지므로, spanning tree가 포함되어있는 것은 자명하다.

노드가 N개인 그래프의 spanning tree는 N-1개의 edge를 가지게 된다.

이 문제를 해결하는 아이디어를 그대로 적는 대신, 풀이를 떠올릴 수 있는 관찰만을 기록해둘 것이다.

Kruskal(크루스칼) 알고리즘을 한 색깔의 에지들의 집합에 적용하면, 그 에지들을 이용하여 사이클이 없게끔 에지를 최대 몇 개 배치할 수 있는지 알 수 있다. 이 최대 개수의 배치에서 다른 그 색깔의 에지를 놓는다면 사이클이 생길 수밖에 없으므로, 이 배치를 포함하는 전체 그래프의 spanning tree의 나머지 에지는 다른 색깔의 에지로 채워지게 될 것이다. (그러한 spanning tree가 존재한다는 것은 조금 생각하면 알 수 있다.)

아래는 제출한 소스코드이다.

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

int R[1001];
int B[1001];

void init(int N) {
	for (int i = 1; i <= N; i++) {
		R[i] = B[i] = i;
	}
}
int findf_R(int x) {
	if (x == R[x]) return x;
	else return R[x] = findf_R(R[x]);
}

int findf_B(int x) {
	if (x == B[x]) return x;
	else return B[x] = findf_B(B[x]);
}

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

	int N, M, K; cin >> N >> M >> K;
	while (N != 0) {
		init(N);
		int cntR = 0, cntB = 0;
		
		while (M--) {
			char c; int f, t; cin >> c >> f >> t;
			if (c == 'R') {
				f = findf_R(f), t = findf_R(t);
				if (f == t) continue;
				cntR++;
				R[t] = f;
			}
			else {
				f = findf_B(f), t = findf_B(t);
				if (f == t) continue;
				cntB++;
				B[t] = f;
			}
		}

		if (N - 1 - cntR <= K && K <= cntB) cout << 1 << '\n';
		else cout << 0 << '\n';

		cin >> N >> M >> K;
	}
}