[BOJ 18267 // C++] Milk Visits

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

 

이번에 볼 문제는 백준 18267번 문제인 Milk Visits이다.
문제는 아래 링크를 확인하자.

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

18267번: Milk Visits

소의 품종이 두 종류인 것을 이용해 풀이를 만들어보자.

 

경로의 시점과 종점이 같은 경우에는 풀이가 자명하므로 다른 경우를 생각해보자. (단, 구현시 이에 대해 예외처리를 해야 할 수 있다는 점은 유의하자.)

 

서로 다른 두 노드 A와 B 사이를 잇는 경로에 'G' 품종의 소가 없으려면 A와 B를 잇는 경로의 모든 소의 품종이 'H'와 같음을 의미한다. 이러한 경우 트리의 에지 중 양 끝 노드 모두 'H'품종 소를 키우는 에지만을 이용해 만든 forest에서 A와 B는 항상 같은 component에 들어있음을 관찰할 수 있다.

 

위 관찰은 반대 품종에 대해서도 같은 방식으로 적용할 수 있다.

 

주어진 그래프에서 두 노드가 같은 component에 들어있는지 확인하는 것은 disjoint set 자료구조를 이용해 빠르게 진행할 수 있다. 이를 이용해 문제를 해결하자.

 

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

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

int N, M;
string s;

int ufG[100001];
int findG(int cur) {
	if (ufG[cur] == cur) return cur;
	else return ufG[cur] = findG(ufG[cur]);
}

int ufH[100001];
int findH(int cur) {
	if (ufH[cur] == cur) return cur;
	else return ufH[cur] = findH(ufH[cur]);
}

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

	cin >> N >> M >> s;

	for (int i = 1; i <= N; i++) ufG[i] = i;
	for (int i = 1; i <= N; i++) ufH[i] = i;

	for (int i = 1; i < N; i++) {
		int x, y; cin >> x >> y;
		if (s[x - 1] == s[y - 1]) {
			if (s[x - 1] == 'G') {
				x = findG(x), y = findG(y);
				ufG[y] = x;
			}
			else {
				x = findH(x), y = findH(y);
				ufH[y] = x;
			}
		}
	}

	while (M--) {
		int x, y; char c; cin >> x >> y >> c;
		if (x == y) {
			if (s[x - 1] == c) cout << 1;
			else cout << 0;
		}
		else if (c == 'G') {
			if (findH(x) == findH(y)) cout << 0;
			else cout << 1;
		}
		else {
			if (findG(x) == findG(y)) cout << 0;
			else cout << 1;
		}
	}
}