[BOJ] 1043 거짓말 C++

개요

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

1043번: 거짓말

골드4 난이도 문제다.

풀이

유니온 파인드로 해결할 수 있다.

진실을 아는 사람의 parent를 -1로 초기화하고, 이를 루트 노드로 사용했다.

파티에 2명이상 있는 경우 Union 연산으로 합쳐주었다.

진실을 아는 사람과 같은 파티에 참석한 사람은 모두 진실을 아는 사람이 된다. (해당 파티에서 진실을 듣기 때문)

때문에 파티들의 첫 번째 손님의 루트 노드를 Find하며 거짓말 할 수 있는 파티인지 판별했다.

떠올리고 구현하는 과정도 마냥 쉽지는 않았는데 왜 골드4였을까,,?

알고보니 N이 작아서 브루트포스로도 해결 가능하다고 한다.

,,,,,

코드

#include<iostream>
#include<algorithm>
using namespace std;
constexpr int LIMIT = 52;

int N, M, T;
int parent[LIMIT];
int party[LIMIT][LIMIT];
int ans;

void Init(int n)
{
	for (int i = 1; i <= n; i++)
		parent[i] = i;
}
int Find(int n)
{
	if (parent[n] == n)return n;
	else if (parent[n] == -1) return -1;

	return parent[n] = Find(parent[n]);
}
void Union(int a, int b)
{
	a = Find(a);
	b = Find(b);

	if (a == b) return;
	else if (a > b) swap(a, b);
	parent[b] = a;
}

int main()
{
	cin.tie(0)->sync_with_stdio(0);

	cin >> N >> M >> T;
	Init(N);

	int n, p, root;
	for (int i = 0; i < T; i++)
	{
		cin >> n;
		parent[n] = -1;
	}
	
	for (int i = 0; i < M; i++)
	{
		cin >> n;
		for (int j = 0; j < n; j++)
		{
			cin >> p;
			party[i][j] = p;
			if (j > 0) Union(party[i][j - 1], party[i][j]);
		}
	}

	for (int i = 0; i < M; i++)
	{
		if (Find(party[i][0]) != -1) ++ans;
	}
	cout << ans;
}