[백준 1043] 거짓말

문제

• 백준 1043

유형

• 구현
• 브루트포스

풀이

시간 복잡도를 정확히는 모르겠지만 O(NM^2)안에는 무조건 끝날거라는 생각을 가지고 N,M이 50이하의 자연수이기 때문에 그냥 구현 문제라고 생각하였다.

M개의 파티를 순회하면서 진실을 아는 사람이 있는 파티의 모든 구성원들을 set에 넣고 다음 파티에 set안에 있는 구성원이 있는지 확인하는 것을 다른 구성원이 set에 들어오지 않을때까지 반복하였다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, k;
set<int> s;
vector<int> v[51];
vector<bool> check(51, true);


int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		int a;
		cin >> a;
		s.insert(a);
	}

	for (int i = 0; i < m; i++) {
		int x,t; cin >> t;
		while (t--) {
			cin >> x;
			v[i].push_back(x);
		}
	}

	while (true) {
		bool c = false;

		for (int i = 0; i < m; i++) {
			bool C = false;
			for (int j = 0; j < v[i].size(); j++) {
				if (check[i] && s.count(v[i][j]) != 0) {
					check[i] = false;
					C = true;
					break;
				}
			}
			if (C) {
				c = true;
				for (int j = 0; j < v[i].size(); j++) {
					s.insert(v[i][j]);
				}
			}
		}

		if (!c) break;
	}

	int ans = 0;
	for (int i = 0; i < m; i++) if (check[i]) ans++;
	cout << ans;




	return 0;
}