백준 12851 자바 풀이

https://www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

몇 번이고 틀린 문제..

골드 등급이라 그런지 엄청 빡셌다. 괴로워 죽는줄! 그래도 다른 분의 블로그를 보고 해결했다.

나는 큐에다 K와 일치하는 숫자를 넣고 빼서 확인하는 방법으로 하려다 보니 check[K] = false 식을 넣어서 계속 진행 하려고 했었는데 이렇게 하면 50% 에서 틀린 값이 나오더라. 뭔가 반례가 있는 듯 한데 잘 모르겠다.

그래서 애초에 마지막 뎁스는 진행하지 않고 next 변수를 이용해서 미리 체크하는 방식으로 했더니 깔끔하게 해결된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class bj12851 {

    static int N, K;
    static boolean[] check;
    static int cnt = 0; //경우의 수
    static int iter = 0; //최단시간 뎁스

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        check = new boolean[100001];

        //N이랑 K가 같거나 N이 더 작을 경우에는 N에서 K를 빼주고 경우의 수는 1만 써주면 된다.
        //이 조건을 잡아야 한다는 걸 깨닫는데 오래 걸렸다.
        if (N >= K) {
            System.out.println((N - K) + "\n1");
            return;
        }

        BFS();

        System.out.println(iter);
        System.out.println(cnt);


    }

    private static void BFS() {
        Queue<Integer> q = new LinkedList<>();
        int num;

        q.offer(N);

        while (!q.isEmpty()) {
            //while문을 벗어나기 위해서는 한 뎁스가 끝났을 때 카운팅이 됐는지(최단거리 찾았는지) 보면 된다.
            if(cnt != 0) return;
            int size = q.size();

            for(int i = 0; i < size; i ++) {
            
               //큐에서 뽑아 visit check를 해준다.
                num = q.poll();
                check[num] = true;
               
               //최단거리 - 1 뎁스에 들어섰다면 큐에 넣을 필요 없이 그 다음에 올 수 있는 숫자가
               //목표하는 숫자(K)인지 확인 후 카운팅을 해주면 된다.
                int next;

                next = num + 1;
                if(next == K) cnt ++;
                else if(num + 1 < check.length && !check[num + 1]) q.offer(next);

                next = num - 1;
                if(next == K) cnt ++;
                else if(num - 1 >= 0 && !check[num - 1]) q.offer(next);

                next = num * 2;
                if(next == K) cnt ++;
                else if(num *2 < check.length && !check[num * 2]) q.offer(next);
            }

            iter ++;

        }
    }
}