BOJ 1043번 거짓말

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

 

게시판을 보니 문제를 이해를 못하시는 분들이 꽤 되시는 것 같아서 문제 설명부터 하겠습니다.

 

간략하게 설명하자면,

진실을 아는 사람을 A, A가 속한 파티에 있는 사람을 B 라고 할 때

A,B 가 속한 모든 파티에서 거짓을 말하면 안됩니다.

 

결국 어떤 파티에서 A가 속하게 되면 => 이 파티 뿐만 아니라 다른 파티에서도 A, B 의 유무를 확인해야 됩니다.

 

예제를 보면

1 2

3

2 3 4

진실을 아는 사람이 만약 0이면 그냥 말그대로 파티 아무데서나 거짓말을 해도 된다가 되지만

만약 여기서 진실을 아는 사람이 2 이면?

파티1은 제외되고 일단 사람2가 파티2, 3에도 존재하는지 확인해봅니다.

파티2에는 사람3밖에 없으므로 거짓을 해도 됩니다. (아직까지는)

파티3에는 사람2가 존재하게 됩니다. => 나머지 사람 3, 4 가 참석할 다른 파티를 확인합니다.

사람3부터 확인하면 사람3은 파티2에 존재합니다. 결국 파티2는 거짓을 하면 안되게 됩니다.

 

이런방향으로 흘러가는 문제입니다.

처음에는 dfs를 통해서 짜보려고 했는데, 구현력이 떨어져서인지 구현이 잘 안되길래 bfs로 변경했습니다.

 

우선적으로 진실을 아는 사람을 모든 파티에 대해 확인할 때,

진실을 아는 사람이 파티에 참가하면 그 파티에 있는 사람까지 큐에 넣었습니다.

 

이 작업이 끝나면 큐에서 하나하나 꺼내면서 모든 파티를 확인해주시면 됩니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
#include <string>
using namespace std;
 
int person, party, know;
vector<int> know_person;
bool party_person[52][52];
bool visit[52][52];
bool dont_party[52];
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    cin >> person >> party >> know;
    for (int i = 0; i < know; i++) {
        int n; cin >> n; know_person.push_back(n);
    }
    for (int i = 0; i < party; i++) {
        int n; cin >> n;
        for (int j = 0; j < n; j++) {
            int m; cin >> m; party_person[i][m] = true;
        }
    }
 
    queue<pair<int, int> > q;
    if (know == 0) cout << party;
    else {
        for (int i = 0; i < party; i++) {
            for (int j = 0; j < know; j++) {
                if (party_person[i][know_person[j]]) {
                    for (int k = 0; k < 52; k++) {
                        if (party_person[i][k])
                            q.push({ i,k });
                    }
                }
            }
        }
 
        while (!q.empty()) {
            int party_idx = q.front().first;
            int p = q.front().second;
            q.pop();
 
            if (visit[party_idx][p]) continue;
            visit[party_idx][p] = true;
            dont_party[party_idx] = true;
 
            for (int i = 0; i < party; i++) {
                if (party_person[i][p]) {
                    for (int j = 0; j < 52; j++) {
                        if (party_person[i][j]) q.push({ i,j });
                    }
                }
            }
        }
 
        int cnt = 0;
        for (int i = 0; i < party; i++) {
            if (dont_party[i] == false) cnt++;
        }
 
        cout << cnt;
    }
 
    return 0;
}