[백준] 1697 - 숨바꼭질 자바

문제

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

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

 

입력

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

 

출력

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

 

예제 입력

5 17

 

예제 출력

4

 

내 코드

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

public class Main_1697 {
	static int N, K;
	
	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());
		
		int max = 100001;
		boolean[] visited = new boolean[max];
		
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(N);
		visited[N] = true;
		int level = 0;
		
		here:
		while(!queue.isEmpty()) {
			
			int queueSize = queue.size();
			for(int i=0; i<queueSize; i++) {
				int temp = queue.poll();
				if(temp == K) {
					System.out.println(level);
					break here;
				}
				
				int[] delta = {temp-1, temp+1, temp*2};
				
				for(int j=0; j<3; j++) {
					if(delta[j]>=0 && delta[j]<max && !visited[delta[j]]) {
						queue.offer(delta[j]);
						visited[delta[j]] = true;
					}
				}			
			}
			level++;
		}
		

		br.close();

	}
}

 

처음에는 visited를 체크해 주지 않아서 시간초과가 나왔고

그 다음에는 ArrayIndexOutOfBoundsErrorExcepton 때문에 고생을 좀 했다.

해결 방법은 queue에 넣을 때 범위를 체크해 주는 것이다

(주의!! max는 100001이고 배열 인덱스의 최댓값은 100000이니까 범위 체크 할땐 <max로!!)