[백준 1043] 거짓말 (C++)

이 문제를 처음 봤을 때는 그냥 각 파티에 진실을 아는 사람이 존재하는지만 체크하는 문제인 줄 알았다. 하지만, 문제를 잘 읽어보면 진실을 아는 사람들이 있는 파티에서는 진실을 이야기 한다고 한다. 이는 해당 파티에 참석했던 사람들이 진실을 알게 된다는 의미이다. 따라서, 진실을 알고 있는 사람이 파티가 열릴 때 마다, 진실을 아는 사람이 추가될 수 있는 상황인 것이다.

그렇다면, 누가 진실을 알게 될 수 있는지를 표시해줘야한다.
먼저, 같은 파티를 참석한 사람들은 서로 들은 이야기를 공유할 수 있다고 가정하자. 이로 인해, 진실을 알고 있는 사람이 파티에 있다면 서로 들은 이야기가 다르므로 지민이가 거짓말쟁이로 소문나게 되는 것이라고 하자.

따라서, 이야기를 공유할 수 있는 관계에 진실을 아는 사람이 존재한다면, 해당 관계에 속한 사람들은 모두 진실을 안다고 할 수 있다.

그렇기에, 먼저 이야기를 공유할 수 있는 관계를 자료구조로 표현해야하는데, 이는 그래프로 쉽게 표현이 가능하다.

이후, BFS나 DFS등의 그래프 탐색 기법들을 이용해서 진실을 아는 사람들을 시작점으로 탐색해나가면 진실을 아는 사람들을 파악할 수 있다.

마지막으로, 파티에 진실을 아는 사람이 참석했는지 체크하면 지민이가 과장할 수 있는지를 판별할 수 있게 된다.

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
set<int> adj[51]; // 이야기를 공유할 수 있는 관계를 그래프로 표현.
vector<int> fact, party[50];
bool vis[51];

void bfs() { // 이야기 공유가능한 관계를 bfs로 탐색
	queue<int> q;

	for (int f : fact) { // 탐색의 시작점을 진실을 아는 사람들로 설정
		q.push(f);
		vis[f] = 1;
	}

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

		for (int nxt : adj[cur]) {
			if (vis[nxt]) continue;
			q.push(nxt);
			vis[nxt] = 1; // 방문을 했다면 진실을 아는 사람
		}
	}
}

bool exaggerate(int i) { // 파티에서 과장해서 이야기 할 수 있는지 확인
	for (int p : party[i]) {
		if (vis[p]) return 0;
	}
	return 1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	while (k--) {
		int x;
		cin >> x;
		fact.push_back(x);
	}

	for (int i = 0; i < m; i++) {
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			party[i].push_back(x);
		}

		for (int idx1 = 0; idx1 < k; idx1++) {
			for (int idx2 = 0; idx2 < k; idx2++) {
				if (idx1 == idx2) continue;
				int u = party[i][idx1], v = party[i][idx2];
				adj[u].insert(v);
				adj[v].insert(u);
			}
		}
	}

	bfs();

	int ans = 0;
	for (int i = 0; i < m; i++) {
		if (exaggerate(i)) ans++;
	}
	cout << ans;
}