백준 1043번 - 거짓말

백준 1043번 - 거짓말

www.acmicpc.net/problem/1043

1043번: 거짓말

 

골드 4 치고는 문제가 짧아 보여서 풀었다.

 

먼저 문제를 이해해보자.

아래는 내가 분석한 문제이다.

 

1. 진실을 아는 사람이 있는 Party에서는 무조건 거짓말 불가!

 

2. Party는 (진실을 말함, 거짓을 말함) 두 가지로 나뉜다. 이때 두 가지를 동시에 겪은 사람은 없어야 된다

-> 즉, 어떤 사람이 진실을 들었다면 그 사람이 간 모든 파티에서 진실을 들어야 한다.

 

3. 만약 진실을 아는 사람이 없다면 m출력

 

크게 3가지 인 것 같았다.

 

이렇게 해서 떠오른 해결방법은 "진실을 알고 있는 사람이 참석한 파티에 참석한 사람들, 이 참석한 파티에 참석한 사람들, 이 참석한 파티에 참석한 사람들...." 이렇게 꼬리에 꼬리를 물고 체킹 해주면 될 것 같았다.

바로 bfs가 떠올랐다.

 

이때 bfs를 어떻게 사용할 것인지가 중요했다.

나는 먼저 인접 리스트를 두 개 만들었다. (이게 bfs로 문제를 푸는 핵심인 것 같다)

 

각 인원에 대한 참여한 회의를 나타내는 인접 리스트와
각 회의에 대한 참여한 인원을 나타내는 인접 리스트 

 

바로 bfs를 사용하지 않고 먼저 '진실을 이미 알고 있던 사람들이 참석한 회의'를 걸러냈다.

for문을 통해 어렵지 않게 구했다.

 

그 뒤, bfs를 통해 '반드시 진실을 말해야 하는 회의'에 참석한 모든 인원들이 참석한 모든 회의들에 대해 체킹 했다.

(말이 계속 꼬리에 꼬리를 물어 이상해 보이지만 사실 정말 정확한 말들이다.)

 

인접 리스트를 2개 만들어놓았기 때문에 회의에 속한 사람들과 각 사람들이 참가한 회의를 쉽게 접근할 수 있었다.

코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
 
// 전역 변수들
int n, m, true_person, party_people, people;
int know_truth[51];
vector<int>v[51]; // 각 인원에 대한 참여한 회의를 나타내는 인접 리스트
vector<int>p[51]; // 각 회의에 대한 참여한 인원을 나타내는 인접 리스트
bool party[51]; // 각 회의가 거짓말을 말해야 되는지 진실을 말해야 되는지 담고 있음
bool check[51]; // bfs에 사용되는 check배열
bool party_check[51]; //bfs에 사용되는 배열
 
void bfs_get_true_party(int x) {
    queue<int>q;
    q.push(x);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        if (party_check[x] == true) continue;
        party_check[x] = true;
        for (int i = 0; i < p[x].size(); i++) { // x번째 파티(무조건 진실만 말하는)에 온 사람들// 모두 검사 
            int nx = p[x][i];
            if (check[nx] == false) {
                check[nx] = true;
                for (int j = 0; j < v[nx].size(); j++) { // 해당 인원이 방문한 모든 파티들을 // q에 넣어줌
                    if (party[v[nx][j]] == false)party[v[nx][j]] = true;
                    q.push(v[nx][j]);
                }
            }
        }
    }
}
 
int main() {
 
    cin >> n >> m;
    cin >> true_person;
 
    for (int i = 0; i < true_person; i++) {
        cin >> know_truth[i];
    }
 
    // 두 개의 인접 리스트 생성
    for (int i = 0; i < m; i++) {
        cin >> party_people;
        for (int j = 0; j < party_people; j++) {
            cin >> people;
            v[people].push_back(i);
            p[i].push_back(people);
        }
    }
 
    // 만약 진실을 알고 있는 사람이 없다면 모든 회의에서 거짓말 가능 -> 회의 개수가 최대값
    if (true_person == 0) {
        cout << m << "\n";
        return 0;
    }
 
    memset(party, false, sizeof(party)); // 초기화
    memset(check, false, sizeof(check)); // 초기화
    memset(party_check, false, sizeof(party_check)); // 초기화
 
    // 진실을 알고 있는 사람의 수만큼 for문을 돌면서 그들과 관련된 파티들을 모두 진실만 말하게 만든다 
    for (int i = 0; i < true_person; i++) {
        int x = know_truth[i];
        for (int j = 0; j < v[x].size(); j++) {
            int nx = v[x][j];
            if (party[nx] == false) party[nx] = true;
        }
    }
 
    // 이제 bfs를 통해 반드시 진실이여야 하는 회의에 참석한 인원들이 참석한 다른 회의들도 걸러냄
    for (int i = 0; i < m; i++) {
        if (party[i] == true) bfs_get_true_party(i);
    }
 
    // 마지막으로 몇 개의 회의가 남았는지 판단
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (party[i] == false) ans++;
    }
 
    cout << ans << "\n";
}

 

중간에 for문에서 i , j를 잘못 써서(j를 써야 되는데 i를 썼다..) 틀리고 난 뒤 30분 동안 고민했다...

이런 실수가 자주 나오니 주의하자..