[Java] 백준 1697번 숨바꼭질

수빈이가 동생한테 가는 최소 시간을 구하는 문제입니다.

수빈이가 할 수 있는 행동은 현재위치를 X라고 했을 때 3가지입니다.
1. X-1
2. X+1
3. X*2

3가지를 하고 해당 시간을 배열에 저장합니다.
바뀐 위치를 큐에 넣습니다. 
큐에서 뺀 값을 위 과정을 반복합니다.

과정에서 더 큰 시간으로 위치에 방문할 경우 방문하지 못하게 하였습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Queue<Integer> q = new LinkedList<>();
		Queue<Integer> qt = new LinkedList<>();
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] ans = new int [100001];
		int t = 0;
		
		for(int i=0; i<=100000; ++i) {
			ans[i] = -1;
		}
		
		q.add(n);
		qt.add(t);
		ans[n] = t;
		while(!q.isEmpty()) {
			int curLoc = q.poll();
			int curTime = qt.poll();
			if(curLoc - 1 >= 0) {
				if(ans[curLoc-1] == -1 || ans[curLoc-1] > curTime + 1) {
					q.add(curLoc - 1);
					qt.add(curTime + 1);
					ans[curLoc - 1] = curTime + 1;
				}
			}
			if(curLoc + 1 <= 100000) {
				if(ans[curLoc+1] == -1 || ans[curLoc+1] > curTime + 1) {
					q.add(curLoc + 1);
					qt.add(curTime + 1);
					ans[curLoc + 1] = curTime + 1;
				}
			}
			if(curLoc * 2 <= 100000) {
				if(ans[curLoc*2] == -1 || ans[curLoc*2] > curTime + 1) {
					q.add(curLoc * 2);
					qt.add(curTime + 1);
					ans[curLoc * 2] = curTime + 1;
				}
			}
		}
		bw.write(ans[m] + "\n");
		bw.close();
	}
}