백준 g4 1043 거짓말 c++

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

1043번: 거짓말

 

문제

사람 수 N과 진실을 아는 사람들 번호가 주어진다.

M개의 파티가 주어진다.

 

각각의 파티에서 지민이는 1. 진실을 아는 사람들이 왔을 때 2. 다른 곳에서 진실을 얘기했는데 똑같은 사람이 파티에 왔을 때, 그 파티에서 거짓말이 아니라 진실을 말해야 한다.

지민이가 거짓말을 할 수 있는 파티의 개수는?

 

풀이

문제를 정리하면, 진실을 아는 사람과 한 번이라도 같은 파티에 참여하는 사람들, 그런 사람들과 같이 파티에 참여하는 사람들(진실을 듣게 되므로) .... 연쇄적으로 같은 파티에 참여하는 사람들은 모두 진실을 들을 수 밖에 없다. 

이런 연쇄적인 경우를 셀 때 그래프가 유용한가보다

 

진실을 아는 사람들과 연결된 사람들의 관계를 그래프로 나타낸 뒤에, 그 사람들이 포함된 파티에선 거짓말을 하지 못한다고 보면 된다.

 

구현

1. adj 파티에서 참가한 대로 기록

- 이때 1, 2, 3 이렇게 참가했다면 인접리스트로 어떻게 기록할 지 고민이 되는데, 누가 누구랑 연결되어 있느냐인 간선이 중요한 게 아니라 연결되어있느냐 아니냐 자체가 중요하기 때문에 그냥 1 -> 2, 1 -> 3 으로 연결해도 상관 없다.

2. 아는 사람 list에서 BFS로 추가로 알게 되는 사람 기록

- 이때 추가로 알게 되는 사람도 BFS를 돌려야 하는가? 돌려야 한다. 왜냐하면 

ex. 1 -> 2 -> 5 / 5 -> 7의 경우 7도 진실을 아는 사람에 포함되어야 하기 때문이다.

3. 아는 사람이 없는 파티 개수 cnt

 

 

+ 주의할 점

for (auto e : a)
{
    a.push_back(...);
}

이런 형식의 range based for loops는 쓸 수 없다.

단순히 무한루프를 떠나서, 

for문은 컨테이너의 시작 ~ 끝으로 도는데 컨테이너의 크기가 변경되면 예상치 못한 원소에 접근할 수 있기 때문에 이상한 값이 나온다.

 

대신 index based for loops를 쓰도록 하자

 

전체 코드

/*boj g4 1043 거짓말*/
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 52
using namespace std;

int N, M, K;
vector<int> know;
vector<int> adj[MAXN];
vector<int> party[MAXN];
int vis[MAXN];
int knowCheck[MAXN];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    cin >> K;
    for (int i = 0; i < K; i++) {
        int x;
        cin >> x;
        know.push_back(x);
    }
    // 1. adj에 파티 참가한 사람들끼리 연결
    for (int i = 0; i < M; i++) {
        int n;
        cin >> n;
        int x, y;
        cin >> x;
        party[i].push_back(x);
        while (--n) {
            cin >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);

            party[i].push_back(y);
        }
    }

    // 2. 아는 사람 list에서 BFS로 연결되어 있는 사람들 기록
    for (int j = 0; j < know.size(); j++) {
        int k = know[j];
        queue<int> Q;

        Q.push(k);
        vis[k] = 1;

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

            for (int a : adj[cur]) {
                if (vis[a]) continue;

                Q.push(a);
                vis[a] = 1;
                know.push_back(a); // -> 이미 아는 사람 list인데 또 추가될 수 있음
            }
        }
    }

    for (int a : know) {
        knowCheck[a] = 1;
    }

    // 3. 아는 사람이 없는 파티 개수 cnt
    int answer = 0;
    for (int i = 0; i < M; i++) {
        bool flag = false;
        for (int p : party[i]) {
            if (knowCheck[p] == 1) {
                flag = true;
                break;
            }
        }
        if (flag == false)
            answer++;
    }

    cout << answer << "\n";
}