developerU
[백준] 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로!!)
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준] 2583 - 영역 구하기 자바 (0) | 2022.03.25 |
---|---|
[백준] 7562 - 나이트의 이동 자바 (0) | 2022.03.24 |
[백준] 1966 - 프린터 큐 자바 (0) | 2022.03.20 |
[백준] 2805 - 나무 자르기 자바 (0) | 2022.03.20 |
[백준] 18111 - 마인크래프트 자바 (0) | 2022.03.20 |
Comments