백준 Gold 4 거짓말

거짓말 (백준 Gold 4)

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

지민이는 파티에서 과장된 이야기 하는 것을 좋아한다
그러나 진실을 알고 있는 사람이 파티에 있다면
과장된 이야기를 하지 못한다

지민이가 과장된 이야기를 할 수 있는 파티의 개수를 구하는 문제

조건

• 진실을 아는 사람이 있는 파티에 참여한 다른 사람들도
  진실을 알게 된다
  

• 지민이는 나중에 진실을 ‘알 것’ 같은 사람이 있는 파티에서도
  과장된 이야기를 할 수 없다
  (파티의 순서는 상관이 없다는 뜻)
  

풀이 방법

처음에는 MST 문제인가 싶었으나
생각해보니 ‘진실’을 아는 사람만을 체크하면 되므로

분리 집합(유니온 파인드)를 응용하면 될 것 같았다

• 진실을 아는 사람은 -1 로 체크
  
• 당장은 진실을 모르더라도 ‘부모’를 설정해둠
  
• 나중에 FindParent를 호출하였을때 -1로 세팅해주는 방식
  
• 마지막에 파티를 돌면서 진실을 알 가능성이 없는 파티만 체크
  

제출 코드

#include<iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int FindParent(vector<int>& pv, int x)
{
	if (pv[x] == -1)
		return -1;

	if (pv[x] == x)
		return x;

	return pv[x] = FindParent(pv, pv[x]);
}

bool Union(vector<int>& pv, int a, int b)
{
	a = FindParent(pv, a);
	b = FindParent(pv, b);
	if (a == b)
		return false;

	if (a == -1)
		pv[b] = -1;
	else if (b == -1)
		pv[a] = -1;
	else
		pv[a] = b;

	return true;
}


int main()
{
	int n, m;
	cin >> n >> m;

	int r;
	cin >> r;

	unordered_set<int> realKnowns;

	for (int i = 0; i < r; i++)
	{
		int t;
		cin >> t;
		realKnowns.insert(t - 1);
	}

	vector<int> partyPeoples(n, 0);
	for (int i = 0; i < n; i++)
	{
		partyPeoples[i] = i;
		if (realKnowns.find(i) != realKnowns.end())
			partyPeoples[i] = -1;
	}

	vector<vector<int>> ttv;
	for (int i = 0; i < m; i++)
	{
		int t;
		cin >> t;

		vector<int> tv;
		for (int j = 0; j < t; j++)
		{
			int t2;
			cin >> t2;
			t2--;
			tv.push_back(t2);
		}

		for (int j = 0; j < t; j++)
		{
			for (int k = j + 1; k < t; k++)
			{
				Union(partyPeoples, tv[j], tv[k]);
			}
		}

		ttv.push_back(tv);
	}

	int ans = m;
	for (auto& tv : ttv)
	{
		bool bCan = true;

		for (int i : tv)
		{
			if (FindParent(partyPeoples, i) == -1)
			{
				bCan = false;
				break;
			}
		}

		if (bCan == false)
			ans--;
	}
	cout << ans;

	return 0;
}

결과

크루스칼의 변형 같은 문제이지만
사실 MST 라 하기엔 애매하여 Union Find를 적용하여 풀 수 있었다