BaekJoon 1043번: 거짓말(C++)

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

1043번: 거짓말

풀이법

1) 그래프의 개념에서 접근하여, 연결된 값들을 확인하는 것이 중요하다.

2) 진실을 아는 사람이 참가한 파티에 있는 모든 사람은 주인공인 지민이가 거짓말을 하는 것을 알게 된다.

3) visited배열과 while문을 활용하여 더 이상 새로운 값으로 갱신 되지 않았을 때, 최종 결과를 구하는 것이 중요하다. (값이 바뀌는 과정에서 중간 결과를 구하려 하면 오답이 나올 수 있다.)

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

int n, m;
int t;
bool visited[51];
int arr[51][51];
int ans;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	cin >> t;
	for (int p = 0; p < t; p++)
	{
		int a;
		cin >> a;
		visited[a] = true;
	}
	for (int i = 0; i < m; i++)
	{
		int col;
		cin >> col;
		bool check = false;
		for (int j = 0; j < col; j++)
		{
			cin >> arr[i][j];
			if (visited[arr[i][j]])
				check = true;
		}
		if (check == true)
		{
			for (int j = 0; j < col; j++)
				visited[arr[i][j]] = true;
		}
	}
	bool p = true;
	while (p==true)
	{
		p = false;
		for (int i = 0; i < m; i++)
		{
			bool check = false;
			for (int j = 0; j < 51; j++)
			{
				if (arr[i][j] == 0)
					break;
				if (visited[arr[i][j]])
					check = true;
			}
			if(check==true)
			{
				for (int j = 0; j < 51; j++)
				{
					if (arr[i][j] == 0)
						break;
					if (visited[arr[i][j]] == false)
					{
						visited[arr[i][j]] = true;
						p = true;
					}
				}
			}
		}
	}
	for (int i = 0; i < m; i++)
	{
		bool check = false;
		for (int j = 0; j < 51; j++)
		{
			if (arr[i][j] == 0)
				break;
			if (visited[arr[i][j]])
				check = true;
		}
		if (check == false)
			ans++;
	}
	cout << ans;
}