[백준 19538번] [BFS] 루머

대략적으로 그래프를 타고 넘어가면서 전파하는 양상이라는 것을 문제를 읽어보면 쉽게 판단할 수 있다.

처음에 생각한 방법은 DFS인데, 중간에 문제점이 있다는 것을 파악하고 포기하였다.

 

예를들어 DFS를 타고 넘어가면서 8분 정도에 특정 노드에 전파할 때 절반을 넘었다고 가정해보자.

단순하게 8분을 전파시점으로 생각하기 쉬우나, 이렇게 단순하게 접근하면 안된다.

예를 들어 다른 간선에서는 4분에 해당 노드에 접근을 시도했을 수도 있기 때문이다. 즉, 해당 간선을 기준으로 만족한다고 하여 그것이 가장 짧은 시간임을 보장할 수가 없게 된다.

 

따라서 이 부분에서 BFS를 강구한 것이다.

즉, 같은 시간에 전파되는 것들을 모두 다 처리하고 넘어가야 해당 노드에 전파되는 시점의 대소비교가 가능해진다.

 

귀찮아서 BFS를 큐로 구현안하고, Recursion으로 구현하였다. (메모리를 아끼려면 아무래도.. queue가 훨씬 더 좋겠다.)

아는 것처럼, 재귀를 통해 BFS를 구할 경우에는 따로 vector 컨테이너로 저장해두어야 한다.

추가적으로 minute가 중요하므로 bfs 함수 안에 minute argument를 넣어야 한다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
vector<int> data_store[200001];
int rumor_store[200001];
int spread_num[200001];
int N, M;

void bfs(int minute, vector<int> spread_store){
    vector<int> next_spread;

    for(int j = 0; j < spread_store.size(); j++){
        int spreader = spread_store[j];
        for(int i = 0; i < data_store[spreader].size(); i++){
            // 절반 넘는지 체크
            if((double)spread_num[data_store[spreader][i]] + 1 >= (double)data_store[data_store[spreader][i]].size() / 2){
                // 전파가 아얘 안된 상태
                if(rumor_store[data_store[spreader][i]] == -1){
                    rumor_store[data_store[spreader][i]] = minute + 1;
                    next_spread.push_back(data_store[spreader][i]);
                    spread_num[data_store[spreader][i]]++;
                }
                // 전파가 전에 되기는 했는데 더 빨리 전파가 될 수 있는 경우
                else continue;
            }
            else spread_num[data_store[spreader][i]]++;
        }
    }
    if(next_spread.empty()) return;
    dfs(minute + 1, next_spread);
    return;
}

int main(void){
    fastio;
    memset(rumor_store, -1, sizeof(rumor_store));
    memset(spread_num, 0, sizeof(spread_num));
    cin >> N;

    for(int i = 1; i <= N; i++){
        while(true){
            int temp;
            cin >> temp;
            if(temp == 0) break;
            data_store[i].push_back(temp);
        }    
    } // 저장정보 저장

    cin >> M;

    vector<int> spread;
    for(int i = 0; i < M; i++){
        int temp;
        cin >> temp;
        spread.push_back(temp);
        rumor_store[temp] = 0;
    }// 유포자 저장
    dfs(0, spread);

    for(int i = 1; i <= N; i++){
        cout << rumor_store[i] << " ";
    }
    cout << "\n";

    return 0;
}