12851

[geonnho0]

문제 링크

[geonnho0]

현재 인덱스에 + 1, - 1, * 2 를 한 값을 구한 뒤, 새로운 인덱스의 범위가 유효하다면, 해당 인덱스에 처음 방문하거나, 가장 빠르게 도달한 방법 중 하나라면, 큐에 삽입하여 bfs를 계속하면 돼요.

bfs는 시간 순으로 차례대로 방문하기 때문에, 만약 poll한 인덱스에 방문한 시간이 K에 도달하는 시간보다 느리면, 큐에 있는 인덱스들은 방문할 필요가 없어요. 이미 K에 도달하는 시간보다 전부 느리기 때문이에요.

코드

public class Main {

    static int N, K, min, count,MAX = 100005;
    static int[] time = new int[MAX];

    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());
        if (N >= K) System.out.print(N - K + "\n1");
        else {
            bfs();
            System.out.print(min + "\n" + count);
        }
    }

    static void bfs() {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(N);
        time[N] = 1;
        min = Integer.MAX_VALUE;
        while (!queue.isEmpty()) {
            int curr = queue.poll(), currTime = time[curr];

            if (min < currTime)
                return;

            for (int i = 0; i < 3; i++) {
                int next;
                if (i == 0) next = curr + 1;
                else if (i == 1) next = curr - 1;
                else next = curr * 2;

                if (next < 0 || next >= MAX) continue;

                if (next == K) {
                    min = currTime;
                    count++;
                }

                if (time[next] == 0 || time[next] == currTime + 1) {
                    queue.offer(next);
                    time[next] = currTime + 1;
                }
            }
        }
    }

}