[BOJ/백준][Gold4] 19538 : 루머 (C++)

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

19538번: 루머

 

 

[난이도] Gold4
[유형] BFS

[풀이]
최초 유포자들부터 queue에 넣고 bfs를 돌려주면 됩니다.
주의할 점이 루머를 믿는 사람에 인접한 사람을 검사할 때,
그 사람의 주변에 루머를 믿는 사람이 절반 이상이어도 바로 visit 체크를 하면 안되고
모든 검사가 끝난 뒤에 한번에 q에 넣고, visit 체크를 해주어야 합니다.
왜냐하면 다음 검사에 영향을 받을 수 있기 때문입니다.

 

#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
vector<int> adj[200001];
int N,M,visit[200001],ip,ans[200001];
queue<int> q;
int main(){
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        while(1){
            scanf("%d",&ip);
            if(ip==0) break;
            adj[i].push_back(ip);
        }
    }
    memset(ans,-1,sizeof(ans));
    scanf("%d",&M);
    for(int i=0;i<M;i++) {
        scanf("%d",&ip);
        q.push(ip);
        visit[ip]=1;
        ans[ip]=0;
    }
    int time=1;
    while(!q.empty()){
        int sz = q.size();
        vector<int> tmp;
        while(sz--){
            auto qf = q.front(); q.pop();

            for(auto nxt : adj[qf]){
                if(!visit[nxt]){
                    int cnt=0;
                    for(auto nadj : adj[nxt]){
                        cnt+=visit[nadj];
                    }
                    if(adj[nxt].size() <= 2*cnt){
                        tmp.push_back(nxt);
                        ans[nxt]=time;
                    }
                }
            }
        }
        for(auto t : tmp){
            q.push(t);
            visit[t]=1;
        }
        time++;
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/19538.cpp