[BFS]백준 19538번 루머

백준 19538번

루머

처음 풀어보는 BFS 문제라 아예 감이 안왔다. 무엇인지는 알고 있는데 구현이 어떤지는 전혀 몰라서.. 찾아보니 Queue를 이용하는 문제였다.

다만 입력 부분이 조금 복잡해 구조체를 사용했는데, 이런 단순 구현 대신 알고리즘이나 자료구조를 더 활용하는 법을 익히는 게 중요할 것 같다.

우선 실험 참여자들은 하나의 구조체로 정의되는데, 구조체는

• 주변인 정보가 담긴 벡터
• 믿기 시작한 시간
• 믿음 여부
• 주변인들 중 믿는 주변인 수

의 멤버를 가진다.

입력을 모두 처리 및 초기화 한 뒤에, 최초 유포자를 큐에 집어넣는다. 이 때 최초 유포자는 시간을 0, 믿음을 true로 설정한 뒤 집어넣는다.

그리고 시간은 1부터 시작한다.

만약 큐의 front 가 믿음을 가진 경우라면

front의 주변인들을 순회하며 각 주변인들의 {주변인들 중 믿는 주변인 수} 멤버를 증가시킨다.

증가시킨 후 해당 주변인이 믿음을 가지는 조건을 만족하는지를 확인한다.

만약 믿음을 가지는 조건을 만족하는 경우

상태 정보를 업데이트 한다.

이 때, 시간 정보는 자신에게 믿음을 전파한 실험 참가자의 시간 + 1 로 정한다.

queue 에 집어넣는다.

만약 큐의 front가 믿음을 가지지 않는다면

넘어간다.

시간 정보를 업데이트 하는 부분에서 생각이 잘 안나 하루를 소비했다.

무조건 자신에게 현재 루머를 전파해준 참가자보다 1 늦은 시간에 소문을 듣게 되는 것인데,, 왜 그렇게 생각을 못했는지 모르겠다.

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

using namespace std;

struct human{
    vector<int> adj;
    int adj_belief;
    int time;
    bool belief;
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    //how many people?
    int population;
    cin >> population;
    //operating queue
    queue<struct human> q;
    //total human group
   vector<struct human> group;
   //initialize human
   for(int i=0;i<population;i++){
       struct human tmp;
       tmp.belief = false;
       tmp.time = -1;
       tmp.adj_belief = 0;
       //put human into the group
       int temp=-1;
       while(temp != 0 && cin >> temp){
           //update adjacent info
           if(temp != 0) {
               tmp.adj.push_back(temp);
            }
        } 
        group.push_back(tmp);
   }
   //how many spreaders in the group
   int spreader_num;
  cin >> spreader_num;
  vector<int> spreader; 
  for(int i=0;i<spreader_num;i++){
      int temp;
      cin >> temp;
      //put spreaders into the group (root)
      //spreaders believe themselves.
      group[temp-1].time = 0;
      group[temp-1].belief = true;
      q.push(group[temp-1]);
  } 
  //set time to 1
  int t=1;
 while(!q.empty()){
      struct human speaker = q.front();
      q.pop();
      if(speaker.belief){
          for(int i=0;i<speaker.adj.size();i++){
              struct human *subject = &group[speaker.adj[i]-1]; 
              subject->adj_belief++;
              if(subject->belief==false && subject->adj_belief * 2 >= (float)subject->adj.size()){
                  subject->belief=true;
                  subject->time = speaker.time+1;
                  q.push(*subject);
              }
          }
          
        } 
     if(q.front().time != speaker.time){
         t++;
     }
    }
  for(int i=0;i<group.size();i++){
      cout << group[i].time << " ";
  }
}