문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

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

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제1-입력

5 17

예제1 - 출력

2

앞서 풀어봤던 1697번과 다른 점은 순간이동시에는 시간이 증가하지 않는다는 점이다. 이 부분 때문에 이미 방문한 적이 있는 위치여도 다시 방문했을때 시간이 단축되는 경우가 발생할 수 있기 때문에 이를 고려해 코드를 작성했다.

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

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

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        br.close();

        int[] visited = new int[100001];
        Arrays.fill(visited, -1);
        Queue<Integer> queue = new LinkedList<>();

        int now = n;
        queue.offer(n);
        visited[now] = 0;

        while (!queue.isEmpty()) {
            now = queue.poll();

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

                if(temp < 0 || temp > 100000)
                    continue;

                if(visited[temp] == -1){
                    if(i != 0)
                        visited[temp] = visited[now] + 1;
                    else
                        visited[temp] = visited[now];

                    queue.offer(temp);
                }
                else{
                    if(i == 0  && visited[temp] > visited[now]){
                        visited[temp] = visited[now];
                        queue.offer(temp);
                    }
                    else if(i != 0 && visited[temp] > visited[now] + 1) {
                        visited[temp] = visited[now] + 1;
                        queue.offer(temp);
                    }
                }
            }
        }
        System.out.println(visited[k]);
    }
}