거짓말 1043

문제

접근 방법

처음에는 간단한 구현 문제인 줄 알았다. 그래서 값을 저장해줄 필요 없이 바로 배열에 적용하고 끝내면 되는 줄 알았는데 틀렸었다.
이 문제는 거짓말을 판단할 수 있는 능력이 전파된다고 생각하면 된다.
처음 파티에서 거짓말을 하고 두 번째 파티에서 다시 만났을 때 거짓말하는 것이 허용이 안 되고 진실을 들은 사람은 다른 사람에게 진실을 전파할 수 있다는 것이다.
즉 진실이 전염되는 것이다.
해결하기 위해선 사람마다 파티를 저장하고 파티마다 사람을 저장하여 이미 지나간 경우에도 다른 사람에게 알릴 수 있게 하였다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int N, M, X, cnt = 0;
    cin >> N >> M;
    queue<int> bfs;
    vector<vector<int>> party(M, vector<int>()), human(N + 1);
    vector<vector<bool>> lieFind(2, vector<bool>(N + 1));
    cin >> X;
    while (X--)
    {
        int num;
        cin >> num;
        lieFind[0][num] = true;
    }
    while (M--)
    {
        int Y;
        cin >> Y;
        while (Y--)
        {
            int num;
            cin >> num;
            party[M].push_back(num);
            human[num].push_back(M);
        }
    }
    for (int i = 1; i <= N; ++i)
    {
        if (!lieFind[0][i] || lieFind[1][i])
            continue;
        bfs.push(i);
        while (!bfs.empty())
        {
            int cur = bfs.front();
            bfs.pop();
            for (int j : human[cur])
            {
                for (int k : party[j])
                {
                    if (lieFind[1][k])
                        continue;
                    lieFind[1][k] = true;
                    bfs.push(k);
                }
            }
        }
    }
    for (auto i : party)
    {
        bool isLie = false;
        for (int j : i)
        {
            if (lieFind[1][j])
            {
                isLie = true;
                break;
            }
        }
        if (!isLie)
            ++cnt;
    }
    cout << cnt;
    return 0;
}

풀이

진실의 전염이라고 생각하면 쉽게 풀릴 것이다.
처음에 엄청 간단한 문제인 줄 알고 접근했다가 큰코다쳤다.