BOJ 19538 - 루머

www.acmicpc.net/problem/19538

19538번: 루머

 

이 문제는 시간 제한이 10초 이며, BFS 로 순회하면서 이중 포문을 돌리더라도 시간초과가 나지 않는다

 

루머 최초 유포자는 0의 값을 갖도록 초기화 시키고 나머지는 전부 -1 을 갖게 만든다

BFS 로 순회할 것이므로 초기화 작업시에 큐에 미리 최초 유포자 정보를 넣는다.

 

큐를 돌면서 현재 노드를 기준으로 인접한 다음 노드가 있는지 찾기위해 반복문을 실행한다

 

인접한 다음 노드가 -1 의 값을 갖고 있으면, 그 노드는 아직 루머가 유포되지 않은 노드이므로

그 다음노드를 기준으로 다른 인접한 노드들을 찾는다. 

찾으면서 인접한 노드들 중 루머를 이미 믿고 있는 사람들이 있다면 찾아내어 갯수를 센다

 

절반이상이 믿고 있으면 갱신하고 아니면 다음 차례로 넘어간다.

 

 

- C++

#include <cstring>
#include <iostream>
#include <queue>
#include <vector> 
 
#define MAX 200001 
 
using namespace std;
 
int N, M; // 사람수, 최초 유포자 수 
vector<int> adj[MAX]; // 인접행렬 
int rumor[MAX]; // 루머 믿는 시간 
queue<pair<int, int>> q; // 노드 번호, 시간 
 
void solve() {
    while(!q.empty()) {
        int node = q.front().first;
        int time = q.front().second;
        q.pop();
        
        for (auto next_node : adj[node]) {
            if (rumor[next_node] == -1) { // 최초 유포자가 아닌 경우 
                int cnt = 0; // 인접한 대상 중 루머 믿는 사람 몇명인지 갯수 세기 
                
                for (auto next_next_node : adj[next_node]) {
                    if (~rumor[next_next_node] && rumor[next_next_node] <= time) cnt += 1;
                }
                
                int next_node_size = adj[next_node].size(); // 다음 노드의 전체 인접한 노드 수 중에서 
                int half = next_node_size / 2; // 절반을 추려냄 
                
                if (next_node_size % 2 == 1) half += 1; // 다만 홀수 일땐 짝홀 맞춰야하고 
                
                if (cnt >= half) { // 절반이상이 믿고 있으면 갱신 
                    rumor[next_node] = time + 1;
                    q.push({next_node, time + 1});
                }
            }
        }
    }
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    int num;
    for (int i = 1; i <= N; ++i) {
        while(1) {
            cin >> num;
            if (num == 0) break;
            adj[i].push_back(num);
        }
    }
    
    memset(rumor, -1, sizeof(rumor));
    
    cin >> M;
    
    for (int i = 0; i < M; ++i) {
        cin >> num;
        rumor[num] = 0;
        q.push({num, 0});
    }
    
    solve();
    
    for (int i = 1; i <= N; ++i) cout << rumor[i] << " ";
    
    return 0;
}