풀이하기에 앞서 이 문제는 Union-find 라는 방법으로 푼다는데, 나는 BFS로 해결했음...

추후에 Union-find로도 해결 할 예정.

---

풀이

1. 파티에서 만난 사람들끼리 서로 만났다는 의미로 meet[나][너] 에 체크해줬고,

2. 진실을 아는 사람들을 전부 큐에 넣어서 BFS를 돌린다.

3. 진실을 아는 사람과 만난 모든 사람들을 전부 진실을 아는 사람으로 바꾸어 준다.

그 후 파티들을 체크하면서 진실을 아는 사람이 껴있는지 확인하면서 카운트 한다.

---

코드

#include <bits/stdc++.h>

using namespace std;

int n, m;
int k;
int know_people[51] = { 0, };
int result = 0;
int visited[51] = { 0, };
int meet[51][51] = { 0, };
vector<int> party[51];
queue<int> q;

void bfs()
{
	while (!q.empty())
	{
		int cur = q.front();

		q.pop();

		visited[cur] = 1;
		know_people[cur] = 1;

		for (int i = 1; i <= n; i++)
		{
			if (meet[cur][i] == 1 && !visited[i])
			{
				know_people[i] = 1;
				q.push(i);
			}
		}
	}
}

void solve()
{
	bfs();

	for (int i = 0; i < m; i++)
	{
		int can_gura = 1;
		for (int j = 0; j < party[i].size(); j++)
		{
			if (know_people[party[i][j]])
				can_gura = 0;
		}

		if (can_gura)
		{
			result++;
		}
	}
}


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

	for (int i = 0; i < k; i++)
	{
		int t;
		cin >> t;
		know_people[t] = 1;
		q.push(t);
	}

	for (int i = 0; i < m; i++)
	{
		// 몇명이 파티에 참석하는지?
		int num;
		cin >> num;
		for (int j = 0; j < num; j++)
		{
			int temp;
			cin >> temp;
			party[i].push_back(temp);
		}

		// 누가 누굴 만나는지 기록
		for (int j = 0; j < num; j++)
		{
			for (int k = 0; k < num; k++)
			{
				if (j != k)
					meet[party[i][j]][party[i][k]] = 1;
			}
		}
	}

	solve();

	cout << result;

	return 0;
}

---

후기

알고리즘 풀이 방법을 보니 그래프이론, 자료구조, 분리집합, 그래프탐색 막 이렇게 되있길래
다른 풀이 방법이 있나 찾아봤다.

-> Union-find 라는 방법이 있다고 한다. 같은 그룹을 구분하는 그런 알고리즘이 있나본데
자료구조 시간에 배운 기억이 맞다면 그래프에서 싸이클이 있는지 없는지 확인하는 알고리즘인걸로 안다.
이걸 이때 사용하는게 맞는건지..? 좀 확인해봐야겠다.