수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.

수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다.

순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

수빈이와 동생이 몇 초 후에 같은 위치에 있을 수 있는지 구하는 문제입니다.

구해야 하는 답이 몇 초 인지이고

1초 단위로 걷거나 순간이동이 가능합니다.

즉 가중치가 1이므로 BFS로 가장 빠른 시간을 구할 수 있습니다.

1초 후에 이동할 수 있는 위치들을 모두 BFS 탐색을 합니다.

BFS 탐색을 하다 동생의 위치로 이동했을 때 시간(초)이

정답입니다.

package problem.bfsdfs;

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main_1697 {
    static int n, k;
    static boolean[] visited;
    static int[] position;
    static Queue<Integer> queue = new LinkedList();

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        int answer = bfs(n);
        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        visited = new boolean[200001];
        position = new int[200001];

        br.close();
    }

    public static int bfs(int n) {
        queue.offer(n);
        visited[n] = true;

        while (!queue.isEmpty()) {
            int move = queue.poll();
            if(move * 2 > 200001)
                continue;

            if (move * 2 <= 200001 && !visited[move * 2]) {
                position[move * 2] = position[move] + 1;
                visited[move * 2] = true;
                queue.offer((move * 2));
            }

            if (move >= 1 && !visited[move - 1]) {
                position[move - 1] = position[move] + 1;
                visited[move - 1] = true;
                queue.offer((move - 1));
            }

            if (move <= 200000 && !visited[move + 1]) {
                position[move + 1] = position[move] + 1;
                visited[move + 1] = true;
                queue.offer((move + 1));
            }

            if (visited[k] == true) {
                return position[k];
            }
        }
        return -1;
    }
}