[백준/BOJ] 백준 18267번 : Milk Visits

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

18267번: Milk Visits

 

길의 정보 x, y를 입력받는데, 만약 x와 y가 같은 종류이면 유니온 파인드의 유니온을 통해 같은 그룹으로 묶는다. 그리고 각 친구가 행복한 조건을 만족하는 경우는 두 가지가 될 수 있는데, 첫 번째는 출발지와 목적지가 같은 그룹으로 묶여있고, 그 그룹이 친구가 좋아하는 종류일 때와 두 번째는 출발지와 목적지의 그룹이 다른 경우이다.

 

출발지와 목적지의 그룹이 다른 경우 행복한 조건을 만족하는 이유는, 출발지와 목적지가 다른 그룹이라는 거는, 출발지의 그룹과 목적지의 그룹이 무엇인지와 상관없이 중간에 다른 그룹이 있다는 것을 의미한다. 즉, 어떤 소의 종류를 선호하던지, 친구가 좋아하는 종류를 만날 수 있다.

 

코드

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

int n, m;
string kind;
int parent[100005];
int rank_size[100005];
vector<int> output;

void pre() {
	for (int i = 0; i < 100005; i++) {
		parent[i] = i;
		rank_size[i] = 1;
	}
}

int find(int u) {
	if (parent[u] == u) {
		return u;
	}

	return parent[u] = find(parent[u]);
}

bool merge(int u, int v) {
	u = find(u);
	v = find(v);

	if (u == v) {
		return false;
	}

	if (rank_size[u] < rank_size[v]) {
		parent[u] = v;
	}
	else {
		parent[v] = u;

		if (rank_size[u] == rank_size[v]) {
			rank_size[u]++;
		}
	}

	return true;
}

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

	pre();

	cin >> n >> m;
	cin >> kind;
	kind = " " + kind;

	for (int i = 0; i < n - 1; i++) {
		int x, y;
		cin >> x >> y;

		//인접한 노드가 같은 종류면 하나의 그룹으로 묶는다
		if (kind[x] == kind[y]) {
			merge(x, y);
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		char c;

		cin >> a >> b >> c;

		a = find(a);
		b = find(b);

		//출발지와 목적지가 같은 그룹일때
		//해당 그룹의 소의 종류가 c면 행복한 조건 만족
		if (a == b) {
			if (kind[a] == c) {
				output.push_back(1);
			}
			else {
				output.push_back(0);
			}
		}

		//출발지와 목적지가 다른 그룹일때
		//출발지와 목적지가 다른 그룹이라는거는, 출발지의 그룹과 목적지의 그룹이 무엇인지와 상관없이 중간에 다른 그룹이 있다는것읠 의미한다
		//그러므로 어떤 소의 종류를 선호하던지, c인 소를 만날 수 있다
		else {
			output.push_back(1);
		}
	}

	for (int i = 0; i < output.size(); i++) {
		cout << output[i];
	}

	return 0;
}