숨바꼭질 (1697번)

문제

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

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

입력

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

출력

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

예제 입력 

5 17

풀이방법

import java.util.*;

public class Test {

    public static final int MAX = 1000001;

    

public static void main(String[] args) {

boolean[] check = new boolean[MAX];

int[] dist = new int[MAX];

 

Scanner sc = new Scanner(System.in);

 

int n = sc.nextInt();

int m = sc.nextInt();

 

check[n] = true;

dist[n] = 0;

 

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

 

q.add(n);

int now;

 

while(!q.isEmpty()) {

 

now = q.remove();

 

if(now-1 >= 0 && check[now-1] == false) {

check[now-1] = true;

q.add(now-1);

dist[now-1] = dist[now]+1;

}

 

if(now+1 < MAX && check[now+1] == false) {

check[now+1] = true;

q.add(now+1);

dist[now+1] = dist[now]+1;

}

 

if(now*2 < MAX && check[now*2] == false) {

check[now*2] = true;

q.add(now*2);

dist[now*2] = dist[now]+1;

}

 

}

 

System.out.println(dist[m]);

}

}