[BOJ] 13549 숨바꼭질 3 - JAVA

1. 문제

13549번: 숨바꼭질 3

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

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

---

2. 풀이

BFS로 풀려면 순서가 중요하다.value가 변하지 않는 *2부터 넣은 후에 -1, +1한 값을 넣는다.

import java.io.*;
import java.util.*;

public class BOJ_13549_숨바꼭질3 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int K = Integer.parseInt(st.nextToken());
      int INF = 200001;

      int[] dist = new int[INF];
      boolean[] visited = new boolean[INF];

      Queue<int[]> queue = new ArrayDeque<>();
      queue.offer(new int[]{N,0});

      int idx, value;
      while(!queue.isEmpty()){
         idx = queue.peek()[0];
         value = queue.poll()[1];

         if(visited[idx]) continue;

         visited[idx] = true;
         dist[idx] = value;

         if(idx==K) break;

         if(idx*2<INF && !visited[idx*2]) queue.offer(new int[]{idx*2,value});
         if(idx-1>=0 && !visited[idx-1]) queue.offer(new int[]{idx-1,value+1});
         if(idx+1<INF && !visited[idx+1]) queue.offer(new int[]{idx+1, value+1});
      }

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

   }
}

---

3. 결과

N이 클지 K가 클지 정해지지 않았는데 하나로 정해서 배열 길이를 정했다가 두 번 틀렸다.