[ 백준 19538 - 루머 ]

[ 문제설명 ]

BFS에서 큐의 성질을 이용하면 풀 수 있는 문제이다. 하단의 그림을 보게되면 BFS에서는 큐가 다음과 같은 형태 ( 시간대별 로 차례 대로 들어간다.) 따라서 0일차에서의 노드들에 대해서 BFS를 할 때에는 임시로 다른 큐에 담아 놓았다가 BFS용 큐가 비었을때 임시로 사용하는 큐에서 노드들을 가져와서 원래 큐에 채워넣으면 날짜 별로 구별해서 BFS를 할 수 있게 된다.

나는 기본적으로 BFS문제를 풀 때 다음과 같은 원칙을 지키고 있다.

1. BFS를 시작할때 시작점을 큐에 넣고 방문했다는 표시를 남겨야 한다.
2. 큐에 넣을때, 반드시 방문했다는 표시를 남겨야 한다.
3. 이웃한 원소가 범위를 벗어났는지에 대한 체크를 반드시 해주어야 한다.

따라서 구현 방법이 여러가지가 있을 수 있겠지만 이렇게 큐를 2개 사용해서 푸는게 개인적으로 가장 직관적이가 잘 와닿았다.

그림으로 이해하기

상단의 그림과 같이 BFS용 큐(Q)와 날짜별로 구별해주기 위해서 다음 방문할 노드(원소)들을 임시로 저장하기 위한 큐(SQ)를 사용하였다. 위에서 언급한대로 큐의 성질에 따라서 Q가 비었다는 것은 1일이 지났다는 것을 의미하므로 Q가 비면 SQ에 잠시 모아놓았던 노드들의 정보를 Q에 옮기고 이와 동시에 해당 노드에 방문했다는 표시를 남겨주면 된다.

[ 소스코드 원본 ]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> graph[200002];
int vis[200002] = {0,};

void init(){
  ios::sync_with_stdio(0);
  cin.tie(0);
}

int main(){
  init();

  for(int i = 0; i < 200002; i++){
    vis[i] = -1;
  }

  int V = 0;
  queue<int> Q;
  int start_num = 0;

  cin >> V;
  for(int i = 1 ; i <= V; i++){
    while(1){
      int v;
      cin >> v;
      if(v == 0) break;
      graph[i].push_back(v);
    }
  } // 기본적인 입력 adjacent list 형태로 그래프 저장

  cin >> start_num;

  for(int i = 0; i < start_num ; i++){
    int start = 0;
    cin >> start;
    vis[start] = 0;
    Q.push(start);
		// BFS를 이용하기 위하여 초기 값들을 Q에 push()
  }

  queue<int> SQ; // small queue 시간 순서별로 구별하기 위해 사용

  while(!Q.empty()){   
    int cur = Q.front(); Q.pop();

    for(int i = 0 ; i < graph[cur].size() ;i++){
      int nx = graph[cur][i];
      if(vis[nx] != -1) continue;
      
      int cnt = 0;
      for(int j = 0; j < graph[nx].size(); j++){
        if( vis[graph[nx][j]] != -1) cnt++;
      }

      if(graph[nx].size() > cnt * 2) continue;
      SQ.push(nx);
    }

    if(Q.empty()){ // Q가 비었다는 것은 하루가 지났다는 것
      while(!SQ.empty()){ // 해당 시간대에 감염이 된 node들에 시간을 표시한다.
          int node = SQ.front(); SQ.pop();
          vis[node] = vis[cur] + 1;
          Q.push(node);
      }
    }
  }

  for(int i = 1 ; i <= V ; i++){
    cout << vis[i] << ' ';
  }

  cout << "\n";

}

참조

위 설명에서 사용된 이미지와 설명의 일부는 바킹독님의 유트브와 바킹독님의 블로그의 강의내용과 강의 자료에서 발췌하였습니다.