[BOJ] 13913 숨바꼭질 4 - JAVA

1. 문제

13913번: 숨바꼭질 4

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

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

 

첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다.

---

2. 풀이

입력

save배열을 만들어서 전부 -1로 초기화한다. N번 위치에 -2를 넣어서 시작 지점을 구분한다.

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 END = 100000;

//직전 위치 저장
int[] save = new int[END + 1];
Arrays.fill(save, -1);
save[N] = -2;

 

BFS

save배열은 배열 인덱스에 해당하는 위치에 도달하기 직전의 위치를 저장한다.

4
5 10 9 18 17

이 예시에서는 이렇게 저장된다.

save[5] = -2 (시작, N)
save[10] = 5
save[9] = 10
save[18] = 9
save[17] = 18

 

따라서 queue에 N을 넣고 queue가 비거나 queue.poll()이 K일 때까지 반복하면서 탐색한다.

현재 위치에서 *2, +1, -1 범위가 가능한지, 방문한 적 없는지 체크한다. 방문 가능하다면 큐에 다시 넣는다. 

다음 조건문이나 반복문으로 가기 전에 *2,+1,-1위치가 K와 동일한지 확인한다면 시간을 줄일 수(는) 있다. 대신 코드가 조금 더럽다. 여기에서는 주석처리 해두었다. 주석을 풀고 돌릴 때도 7번째 줄을 주석처리하면 안된다. N==K인 경우가 있을 수 있기 때문이다.

 

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(N);

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

   if (now * 2 <= END && save[now * 2] == -1) {
      save[now * 2] = now;
      queue.offer(now * 2);
      //if(now*2==K) break;
   }
   if (now + 1 <= END && save[now + 1] == -1) {
      save[now + 1] = now;
      queue.offer(now + 1);
      //if(now+1==K) break;
   }
   if (now - 1 >= 0 && save[now - 1] == -1) {
      save[now - 1] = now;
      queue.offer(now - 1);
      //if(now-1==K) break;
   }
}

 

경로 저장

ArrayList를 하나 만들고 N부터 K까지 어떻게 도달했는지 경로를 저장한다. save[N]에 -2를 저장했으므로 save[find]가 -2가 아닐때만 반복한다.

int find = K;
ArrayList<Integer> list = new ArrayList<>();
while (save[find] != -2) {
   list.add(find);
   find = save[find];
}

 

출력

1.  먼저 list의 사이즈를 sb에 더한다. list에는 현재 N이 없기 때문에 사이즈에서 1을 빼지 않아도 된다.

2.  sb에 N을 더한다.

3.  list의 맨 끝부터 처음까지 반복하면서 sb에 더한다.

4.  출력한다.

StringBuilder sb = new StringBuilder();
sb.append(list.size()).append('\n');
sb.append(N).append(' ');
for (int i = list.size() - 1; i >= 0; i--) {
   sb.append(list.get(i)).append(' ');
}

System.out.println(sb);

 

전체 코드

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

public class BOJ_13913_숨바꼭질4 {
   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 END = 100000;

      //직전 위치 저장
      int[] save = new int[END + 1];
      Arrays.fill(save, -1);
      save[N] = -2;

      Queue<Integer> queue = new ArrayDeque<>();
      queue.offer(N);

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

         if (now * 2 <= END && save[now * 2] == -1) {
            save[now * 2] = now;
            queue.offer(now * 2);
            //if(now*2==K) break;
         }
         if (now + 1 <= END && save[now + 1] == -1) {
            save[now + 1] = now;
            queue.offer(now + 1);
            //if(now+1==K) break;
         }
         if (now - 1 >= 0 && save[now - 1] == -1) {
            save[now - 1] = now;
            queue.offer(now - 1);
            //if(now-1==K) break;
         }
      }

      int find = K;
      ArrayList<Integer> list = new ArrayList<>();
      while (save[find] != -2) {
         list.add(find);
         find = save[find];
      }

      StringBuilder sb = new StringBuilder();
      sb.append(list.size()).append('\n');
      sb.append(N).append(' ');
      for (int i = list.size() - 1; i >= 0; i--) {
         sb.append(list.get(i)).append(' ');
      }

      System.out.println(sb);
   }
}

---

3. 결과

(사진 아래에서부터 1)

1.  마지막 list에 N을 넣고 SB에 더했는데, 깜빡하고 list.size()에서 1을 빼주지 않아서 틀렸다.

2.  잘 맞는가 했더니 50퍼센트 정도에서 메모리초과가 났다. 알고보니 문제의 위치 범위가 0을 포함하기 때문에 save배열을 0으로 초기화하면 안되는 거였다. 그래서 전부 -1로 초기화하고 save[N]에는 -2를 저장하는 걸로 해결했다.

3.  첫번째 성공(글에서 주석처리된 부분이 모두 살아있었다.)

4.  BFS에서, 다음 원소로 가기 전에 그 원소가 K와 동일한지 체크하는 조건문을 빼서 돌려봤다. (글에서 주석처리된 부분) 탐색하는 기간이 길어진 만큼 시간이 조금 더 걸렸다.