[알고리즘 19.1.8] BFS - 전염병

문제

---

철수네 마을에는 갑자기 전염병이 유행하기 시작하였다. 이 전염병은 전염이 매우 강해서, 이웃한 마을끼리는 전염되는 것을 피할 수 없다.
철수네 마을은 1번부터 N번까지 번호가 매겨져 있다. 철수네 마을의 구조는 꽤나 복잡한데, i번 마을에서 출발하면 i * 2 번 마을에 갈 수 있고, 또한 i / 3(i를 3으로 나눈 몫) 번째 마을에도 갈 수 있다. 전염병은 사람에 의하여 옮는 것으로 알려져 있다. 따라서 i번 마을에 전염병이 돌게 되면, i * 2 번 마을과 i / 3(i를 3으로 나눈 몫) 번 마을 역시 전염병이 돌게 된다.
K번 마을이 가장 처음으로 전염병이 돌기 시작했을 때, 전염병이 돌지 않는 마을의 개수를 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 전체 마을의 개수 N과, 처음으로 전염병이 돌기 시작한 마을 번호 K가 주어진다. ( 1 ≤ N, K ≤ 100,000 ) 

출력

---

전염병이 돌지 않는 마을의 개수를 출력한다.

 

예제 입력

10 3

예제 출력

4

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
#include<queue>
using namespace std;
 
const int MAX = 100005;
 
//마을 배열, 전염병 시작 마을
int arr[MAX]={0,};
int n, k;
 
//전염병 걸린 마을을 담을 queue
queue <int> q;
 
void BFS(){
  if(q.empty()) return;
  int town = q.front();
  q.pop();
  
  int a = town*2;
  int b = town/3;
  
  if(a<=n && arr[a]==0){
    q.push(a);
    arr[a]=1;
  }
  
  if(arr[b]==0){
    q.push(b);
    arr[b]=1;
  }
  
  if(!q.empty()) BFS();
}
 
int main(){
  
  scanf("%d %d",&n,&k);
  q.push(k);
  arr[k] = 1;
  
  BFS();
  
  int cnt = 0;
  for(int i=1; i<=n; i++){
    if(arr[i]==0){
      cnt++;
    }
  }
  
  cout<<cnt<<endl;
  
  return 0;
}