[백준/C++] 1043번 거짓말

백준

 

---

🤔문제 이해

진실을 알고 있는 사람들이 파티에 참석하는 경우 그 파티에선 진실만 말해야하고, 순서 상관없이 진실을 한번이라도 듣게 되는 사람들이 참석하는 파티는 진실만 말해야 할 때 과장된 이야기를 할 수 있는 파티의 개수를 구하면 되는 문제이다.

---

💡첫번째 아이디어

진실을 아는 사람이 포함된 파티에 간 사람들을 모두 진실을 알고 있다고 처리해주고 이 과정을 반복하면 진실로 말해야 하는 파티와 과장해서 말해도 되는 파티를 구분해줄 수 있다고 생각했다.

 

🔥풀이🔥

know[i] : i번 사람이 진실을 알면 true, 모르면 false

party_know[i] : i번 파티가 진실을 말해야 하는 파티면 true, 과장해서 말해도 되는 파티면 false

party[i][j] : i번째 파티에 참석한 사람들의 번호를 저장

 

처음 진실을 알고 있는 사람들이 참여하는 파티를 true로 바꿔준다.

진실을 말해야 하는 파티에서 진실을 모르는 사람들을 진실을 알고 있다고 처리해주고, 진실을 알게된 사람들이 포함된 파티들을 진실을 말해야 하는 파티로 처리해준다.

새롭게 진실을 알게되는 사람이 생기지 않을 때까지 위 과정을 반복해주고 party_know의 값이 false인 것의 개수를 세서 출력해준다.

---

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<vector<int>> party;
bool party_know[52];
bool know[52];

bool solve() {
    int flag = 0;
    for (int i = 0; i < m; i++) {
        if (party_know[i]) {
            for (int x: party[i]) {
                if (know[x]) continue;
                know[x] = true;
                flag = 1;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        if (party_know[i]) continue;
        for (int x: party[i]) {
            if (know[x]) {
                party_know[i] = true;
            }
        }
    }
    return flag;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    party.resize(m + 2);

    int a, b;
    cin >> a;
    for (int i = 0; i < a; i++) {
        cin >> b;
        know[b] = true;
    }

    for (int i = 0; i < m; i++) {
        cin >> a;
        for (int j = 0; j < a; j++) {
            cin >> b;
            party[i].push_back(b);
            if (know[b]) {
                party_know[i] = true;
            }
        }
    }
    int flag = 0;
    for (int i = 0; i < m; i++) {
        if (party_know[i]) {
            for (int x: party[i]) {
                know[x] = true;
                flag = 1;
            }
        }
    }

    for (int i = 0; i < m; i++) {
        if (party_know[i]) continue;
        for (int x: party[i]) {
            if (know[x]) {
                party_know[i] = true;
                flag = 1;
            }
        }
    }
    while (flag) {
        flag = solve();
    }

    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (!party_know[i])cnt++;
    }
    cout << cnt;
}