[BOJ] 12851 숨바꼭질 2 - JAVA

1. 문제

12851번: 숨바꼭질 2

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

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

---

2. 풀이

1.  BFS를 이용하되, 한 번 방문한 곳이라도 지금의 depth와 동일하면 다시 방문한다.

2.  2차원 배열을 사용했다. 0번째 칸에는 시간(depth), 1번째 칸에는 경우의 수를 저장한다. 방문여부와 구분하기 위해 N위치일 때도 시간을 1로 설정했다. 따라서 마지막 way[K][0]을 출력할 때 -1을 해야한다.

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

public class BOJ_12851_숨바꼭질 {
   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[][] way = new int[100001][2];//시간, 경우의 수
      Queue<Integer> queue = new ArrayDeque<>();
      way[N][0] = way[N][1] = 1;
      queue.offer(N);

      int END = 100000;
      int now;
      while (!queue.isEmpty()) {
         now = queue.poll();
         if(now==K) break;

         if (now * 2 <= END && (way[now * 2][0] == 0 || way[now * 2][0] == way[now][0] + 1)) {
            if (way[now * 2][0] == 0) {
               way[now * 2][0] = way[now][0] + 1;
            }
            way[now * 2][1]++;
            queue.offer(now*2);
         }
         if (now - 1 >= 0 && (way[now - 1][0] == 0 || way[now - 1][0] == way[now][0] + 1)) {
            if (way[now - 1][0] == 0) {
               way[now - 1][0] = way[now][0] + 1;
            }
            way[now - 1][1]++;
            queue.offer(now-1);
         }
         if (now + 1 <= END && (way[now + 1][0] == 0 || way[now + 1][0] == way[now][0] + 1)) {
            if (way[now + 1][0] == 0) {
               way[now + 1][0] = way[now][0] + 1;
            }
            way[now + 1][1]++;
            queue.offer(now+1);
         }
      }

      System.out.println(way[K][0]-1 + "\n" + way[K][1]);
   }
}

 

---

3. 결과