BOJ 1043 - 거짓말

www.acmicpc.net/problem/1043

1043번: 거짓말

 

처음에 문제 풀때, 진실을 아는 사람의 정보를 담는 배열, 파티를 구성하는 2차원 배열로 문제를 해결하려 했으나, 이전 차례 혹은 다음 차례의 파티에서 진실을 알게 될 경우를 계산하지 못해서 틀렸다

 

#include <bits/stdc++.h>
 
#define MAX 51 
 
using namespace std;
 
int N, M;
bool known[MAX]; // 진실을 아는 사람들  
bool arr[MAX][MAX]; // i 번 파티의 참가자 j, j 가 진실을 알면 true, 모르면 false 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M;
    
    int known_people;
    cin >> known_people;
    for (int i = 0; i < known_people; ++i) {
        int temp;
        cin >> temp;
        known[temp] = true;
    }
    
    for (int i = 0; i < M; ++i) {
        vector<int> participants;
        
        int num_of_participants;
        cin >> num_of_participants;
 
        bool flag = false;
        
        for (int j = 0; j < num_of_participants; ++j) {
            int person;
            cin >> person;
            participants.push_back(person);
            if (known[person]) flag = true;
        }
        
        for (int j = 0; j < participants.size(); ++j) {
            if (flag) {
                // 한사람이라도 진실을 알면 해당파티의 참가자 모두 false
                // 이전 파티중 영향 받을 수 있는 파티 검색
                for (int k = 0; k < i; ++k) {
                    arr[k][participants[j]] = false;
                } 
                arr[i][participants[j]] = false; 
                known[participants[j]] = true; 
            } else {
                // 단 한사람도 진실을 모르면 해당 파티의 참가자 모두 true
                arr[i][participants[j]] = true; 
            }
        }
    }
    
    int answer = 0;
    for (int i = 0; i < MAX; ++i) {
        bool temp = false;
        for (int j = 0; j < MAX; ++j) {
            if (arr[i][j]) {
                // i 번째 파티에 true 가 하나라도 있다면 (즉, 거짓이 )
                temp = true; 
            }
        }
        if (temp) {
            answer++;
        }
    }
    
    cout << answer;
    
    return 0;
}

 

위 처럼 풀어내는게 아니라, 각 파티들을 돌면서, 영향을 받을 수 있는 모든 파티들을 전부 찾아내면서

해당 파티가 거짓이 먹히는 파티인지, 아닌지 섞어내야했다.

그래서 해당 파티가 거짓이 통하는 파티인지 아닌지 판별하기 위해 별도의 또다른 배열 하나를 선언하여 처리해줘야했다.

 

- c++

#include <bits/stdc++.h>
 
#define MAX 51 
 
using namespace std;
 
int N, M; // 참석자, 파티 수 
bool known[MAX]; // 진실을 아는 사람 목록 
bool arr[MAX][MAX]; // i 번째 파티 j 번 참가자 
bool all_known_party[MAX]; // 파티의 모든 참가자가 진실을 아는지 체크 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M;
    
    int num_of_known;
    cin >> num_of_known;
    for (int i = 1; i <= num_of_known; ++i) {
        int temp;
        cin >> temp;
        known[temp] = true;
    }
    
    for (int i = 1; i <= M; ++i) {
        int num_of_party_members;
        cin >> num_of_party_members;
        
        for (int j = 1; j <= num_of_party_members; ++j) {
            int temp;
            cin >> temp;
            arr[i][temp] = true; 
        }
    }
    
    bool flag;
    while(true) {
        flag = false;
        
        for (int i = 1; i <= M; ++i) {
            // i번째 파티의 참가자들이 모두 진실을 알때 
            if (all_known_party[i]) continue;
            
            bool is_someone_known = false;
            for (int j = 1; j <= N; ++j) {
                if (arr[i][j] && known[j]) {
                    is_someone_known = true;
                    break;
                }
            }
            
            // 한 명이라도 진실을 아는 경우 
            if (is_someone_known) {
                for (int j = 1; j <= N; ++j) {
                    if (arr[i][j] && !known[j]) {
                        known[j] = true;
                        flag = true;
                    }
                }
                all_known_party[i] = true;
            }
        }
        
        // 진실을 알 수 있는 멤버의 경우의 수가 더이상 존재하지 않을때 
        if (!flag) break;
    } 
    
    int answer = 0;
    for (int i = 1;  i <= M; ++i)
        if (!all_known_party[i])
            answer++;
            
    cout << answer;
    
    return 0;
}

 

 

 

 

- 참고

octorbirth.tistory.com/440

[BOJ] 백준 1043 거짓말