[백준] 골4 - 거짓말

1043번: 거짓말

문제 설명

각 파티마다 참여하는 사람이 주어진다.

각 파티마다 진실로 말하는 경우와 과장되게 말하는 경우가 있는데, 과장되게 말할 수 있는 수를 구하는 문제이다. 단, 진실을 알고 있는 사람이 주어진다. 각 파티에서 진실을 알고 있는 사람이 있으면 과장되게 말할 수 없다. 또한 어떤 사람에게 있어 어떤 파티에선 과장되게 들었는데 어떤 파티에선 진실로 들으면 안된다.

풀이

각 파티마다 참여하는 사람을 집합에 넣는다. 만약 2개 이상의 파티에 참여한 사람이 있다면 두 집합을 하나의 집합으로 합친다.

이렇게 하는 이유는 진실을 말하는 사람은 해당 파티에 있는 모든 인원을 진실로 듣게하고 그 인원들은 다른 파티에서 또 진실을 퍼뜨릴 것이다. 그러므로 파티끼리 집합으로 묶는 것이다.

따라서 이 문제는 Union-Find 문제이다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int cnt, person;
int parent[51];
vector<int> v[51];
vector<int> knowing;
int before;

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

void Union(int x, int y)
{
	int xr = Find(x);
	int yr = Find(y);

	parent[xr] = yr;
}

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

	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		parent[i] = i;

	cin >> cnt;
	for (int i = 0; i < cnt; i++)
	{
		cin >> person;
		knowing.push_back(person);
	}

	for (int i = 1; i <= m; i++)
	{
		cin >> cnt;
		for (int j = 0; j < cnt; j++)
		{
			if (j >= 1)
			{
				cin >> person;
				Union(before, person);
				v[i].push_back(person);
				before = person;
			}
			else
			{
				cin >> person;
				v[i].push_back(person);
				before = person;
			}
		}
	}

	int answer = m;
	for (int i = 1; i <= m; i++)
	{
		bool flag = false;
		for (auto& person : v[i])
		{
			if (flag)
				break;
			for (auto& known : knowing)
			{
				if (Find(person) == Find(known))
				{
					flag = true;
					break;
				}
			}
		}
		if (flag)
			answer--;
	}

	cout << answer;
	return 0;
}

소감

유니온 파인드 틀을 외우자!

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

void Union(int x, int y)
{
	int xr = Find(x);
	int yr = Find(y);

	parent[xr] = yr;
}

참조

[백준 1043번] 거짓말