[백준/BOJ] 백준 12877번 : 먹이 사슬

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

12877번: 먹이 사슬

유니온 파인드를 이용하여 문제를 해결했는데, 논리적으로 오류가 아닌 것은 유니온 하였다. 이때 parent를 인덱스에 따라 종류를 나누어서 표시했다(1~50000은 A종류, 50001~100000은 B종류, 100001 ~ 150000은 C종류 일 때)

 

코드

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

int n, k;
int result = 0;
vector<int> parent(150001); //(1~50000은 A종류, 50001~100000은 B종류, 100001 ~ 150000은 C종류 일때)
vector<int> rank_size(150001);

//모순이 되지 않는 내용을 유니온하는 방법으로 문제 해결

void Pre()
{
	for (int i = 1; i <= 150000; i++)
	{
		parent[i] = i;
		rank_size[i] = 1;
	}
}

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

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

void Merge(int u, int v)
{
	u = Find(u);
	v = Find(v);

	if (u == v)
		return;

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

	else
	{
		parent[v] = u;

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

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

	Pre();

	cin >> n >> k;

	for (int i = 0; i < k; i++)
	{
		int t, x, y;

		cin >> t >> x >> y;

		//올바른 동물의 번호가 아닌 경우
		if (x > n || y > n || x < 1 || y < 1)
		{
			result++;

			continue;
		}

		//같은종류
		if (t == 1)
		{
			//x가 y를 잡아먹는다고 이전에 나왔을때
			if ((Find(x) == Find(y + n)) || (Find(x + n) == Find(y + (2 * n))) || (Find(x + (2 * n)) == Find(y)))
			{
				result++;
			}

			//y가 x를 잡아먹는다고 이전에 나왔을때
			else if ((Find(y) == Find(x + n)) || (Find(y + n) == Find(x + (2 * n))) || (Find(y + (2 * n)) == Find(x)))
			{
				result++;
			}

			//모순이 아닐때
			else
			{
				Merge(x, y); //A종류끼리 같음
				Merge(x + n, y + n); //B종류끼리 같음
				Merge(x + (2 * n), y + (2 * n)); //C종류끼리 같음
			}
		}

		//x는 y를 먹을때
		else
		{
			//x와y가 같은 종류라고 이전에 나왔을때
			if ((Find(x) == Find(y)) || (Find(x + n) == Find(y + n)) || (Find(x + (2 * n)) == Find(y + (2 * n))))
			{
				result++;
			}

			//y가 x를 잡아 먹는다고 이전에 나왔을때
			else if ((Find(y) == Find(x + n)) || (Find(y + n) == Find(x + (2 * n))) || (Find(y + (2 * n)) == Find(x)))
			{
				result++;
			}

			//모순이 아닐때
			else
			{
				Merge(x, y + n); //A종류는 B종류를 먹음
				Merge(x + n, y + (2 * n)); //B종류는 C종류를 먹음
				Merge(x + (2 * n), y); //C종류는 A종류를 먹음
			}
		}
	}

	cout << result;

	return 0;
}