백준 1043번 거짓말 (C++)

문제 링크 : https://www.acmicpc.net/problem/1043

1043번: 거짓말

문제 풀이는 다음과 같다.

 

1. 먼저 필요한 변수들을 선언해주고 값을 저장해준다.

    int n,m,t,p,pn,ans=0;
    bool ch[51]; // 진실을 아는지 여부
    bool res[51]; // 과장된 이야기를 할 수 있는 파티 여부
    cin >> n >> m;
    vector<int> party[m+1];
    queue<int> q;
    memset(ch,false,sizeof(ch)); // 배열 초기화
    memset(res,false,sizeof(res)); // 배열 초기화
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> pn;
        ch[pn] = true; // 진실을 아는 사람 체크
        q.push(pn); // 큐에 진실을 아는 사람 삽입
    }
    for(int i=1; i<=m; i++){
        cin >> pn; // 파티에 참석하는 사람 수
        for(int j=0; j<pn; j++){
            cin >> p; // 해당 파티에 참석하는 사람
            party[i].push_back(p); // 해당 파티에 참석하는 사람 번호 삽입
        }
    }

 

2. 큐가 빌때까지 while문을 진행한다.

    while(!q.empty()){
        p = q.front();
        q.pop();
        for(int i=1; i<=m; i++){ // 1
            if(find(party[i].begin(),party[i].end(),p)!=party[i].end()){ // 2
                res[i] = true; // 3
                if(party[i].size()>1){ // 4
                    for(int j=0; j<party[i].size(); j++){
                        if(!ch[party[i][j]]){ // 5
                            ch[party[i][j]] = true;
                            q.push(party[i][j]);
                        }
                    }
                }
            }
        }
    }

(1) 1번부터 파티장 갯수까지 for문을 돌려준다. 

(2) [i]번 파티장에 진실을 아는 사람 p가 존재할 경우,

(3) [i]번 파티장은 과장된 이야기를 할 수 없는 파티로 표시해준다.

(4) 만약 [i]번 파티장의 사이즈가 1을 초과할 경우, 해당 파티장에는 진실을 아는 사람 p이외에 다른 사람도 있다는 뜻이다. 이제 다른 사람또한 진실을 알게되었으므로, 

(5) 다른 사람도 진실을 아는 것으로 표시해주고 큐에 삽입한다.

 

3. 1번부터 m번까지의 파티장에서 과장된 이야기를 할 수 있는 파티의 갯수를 세어준다.

    for(int i=1; i<=m; i++) if(!res[i]) ans++; 
    cout << ans << "\n";

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,t,p,pn,ans=0;
    bool ch[51]; // 진실을 아는지 여부
    bool res[51]; // 과장된 이야기를 할 수 있는 파티 여부
    cin >> n >> m;
    vector<int> party[m+1];
    queue<int> q;
    memset(ch,false,sizeof(ch)); // 배열 초기화
    memset(res,false,sizeof(res)); // 배열 초기화
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> pn;
        ch[pn] = true; // 진실을 아는 사람 체크
        q.push(pn); // 큐에 진실을 아는 사람 삽입
    }
    for(int i=1; i<=m; i++){
        cin >> pn; // 파티에 참석하는 사람 수
        for(int j=0; j<pn; j++){
            cin >> p; // 해당 파티에 참석하는 사람
            party[i].push_back(p); // 해당 파티에 참석하는 사람 번호 삽입
        }
    }
    while(!q.empty()){
        p = q.front();
        q.pop();
        for(int i=1; i<=m; i++){
            if(find(party[i].begin(),party[i].end(),p)!=party[i].end()){
                res[i] = true;
                if(party[i].size()>1){
                    for(int j=0; j<party[i].size(); j++){
                        if(!ch[party[i][j]]){
                            ch[party[i][j]] = true;
                            q.push(party[i][j]);
                        }
                    }
                }
            }
        }
    }
    for(int i=1; i<=m; i++) if(!res[i]) ans++; 
    cout << ans << "\n";
    return 0;
}