Baekjoon 1043번 거짓말

문제

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

걸린 시간

02 : 01 : 49 실패

풀이

C++

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

int n, m; // 사람 수, 파티 수
int truth[51]; // index : 참여자 번호, value : 진실 앎 여부
int adj_mat[51][51]; // 0 : 지민
int visited[51];

void bfs(){
    memset(visited, 0, sizeof(visited));
    queue<int> q;
    visited[0] = 1;
    for(int i = 1; i <= n; i++)
        if(truth[i])
            q.push(i);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(int w = 1; w <= n; w++){
            if(adj_mat[v][w]){
                if(!visited[w]){
                    visited[w] = 1;
                    truth[w] = 1;
                    q.push(w);
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    int count, join;
    cin >> count;
    memset(truth, 0, sizeof(truth));
    memset(adj_mat, 0, sizeof(adj_mat));
    vector<vector<int>> party;
    for(int i = 0; i < count; i++){ 
        cin >> join;
        truth[join] = 1;
        adj_mat[0][join] = 1;
        adj_mat[join][0] = 1;
    }
    for(int i = 1; i <= m; i++){ // 파티 번호
        cin >> count;
        vector<int> tmp;
        for(int j = 0; j < count; j++){
            cin >> join;
            tmp.push_back(join);
        }
        party.push_back(tmp);
        for(int j = 0; j < count; j++){
            for(int k = 0; k < count; k++){
                if(j != k){
                    adj_mat[tmp[j]][tmp[k]] = 1;
                    adj_mat[tmp[k]][tmp[j]] = 1;
                }
            }
        }
    }
    bfs();
    int ans = 0;
    for(int i = 0; i < party.size(); i++){
        bool flag = true;
        for(int j = 0; j < party[i].size(); j++)
            if(truth[party[i][j]])
                flag = false;
        if(flag)
            ans++;
    }
    cout << ans << "\n";
    return 0;
}

독해력의 중요성을 또 한번 깨닫게 해주는 문제. 문제를 3번 읽고 나서야 이해한 내용은 다음과 같다.

1. 모든 파티에 참여해야 한다.
2. 거짓말쟁이가 되지 않기 위해선 진실을 아는 사람들이 있는 파티부터 참석해 진실을 이야기해야 한다.

진실을 모르는 사람들이 모인 파티에서부터 과장된 이야기를 한다면, 진실를 아는 사람과 같이 모이게 된 다른 파티에서 거짓말쟁이가 되버린다.

따라서 진실을 아는 사람이 참여하고 있는 파티부터 참석해 나가며 그 파티에서 진실을 들은 사람이 참여하고 있는 파티까지 전부 참여한다.

그렇게 해서 남은 진실을 모르는 사람들만이 모인 파티의 수가 정답이 된다.

이 문제는 그래프 탐색을 이용해 해결할 수 있다.

1. 0번은 지민, 1번부터 50번까지는 파티에 참여한 사람의 번호로 하는 인접행렬을 만든다.
2. 진실을 아는 사람들의 번호가 주어지면 0번 지민이와 연결시킨다.
3. 한 파티에 참여한 사람들의 번호가 주어지면 서로 모두 연결시킨다.
4. 진실을 아는 사람들의 번호를 큐에 추가하고 탐색을 진행한다. (진실을 아는 사람들과 연결된 사람들은 같은 파티에 참여하고 있는 사람이다.)
5. 탐색이 끝나면(진실을 아는 사람들이 모두 정해지면) 모든 파티를 조사하며 진실을 모르는 사람들만이 모인 파티를 찾는다.