전염병

전염병

 

문제

---

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

 

입력

---

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

출력

---

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

 

예제 입력

10 3

예제 출력

4




코드

//전염병

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();


    public static int done[];
    public static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;

        a = sc.nextInt();

        done = new int[a];

        b = sc.nextInt();
        sc.close();

        epidemicBFS(b);
        System.out.println(a - count);

    }

    public static void epidemicBFS(int cur) {

        Queue<Integer> q = new LinkedList<>();

        int data = cur;
        q.offer(data);

        while (!q.isEmpty()) {

            data = q.poll();

            count++;

            int gop = data * 2;
            int nanugi = data / 3;

            if (gop <= done.length && done[gop-1] == 0) {
                q.offer(gop);
                done[gop-1] = 1;
            }
            if (nanugi >= 1 && done[nanugi-1] == 0) {
                q.offer(nanugi);
                done[nanugi-1] = 1;
            }

        }

    }


}