[BOJ] 17071 숨바꼭질 5 - JAVA

1. 문제

17071번: 숨바꼭질 5

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

 

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

---

2. 풀이

두 가지 방식으로 풀었다.

첫 번째는 위치별로 가능한 최소시간을 전부 구한 후 동생 시간 기준으로 답을 알아내는 방법이다.

두 번째는 depth(=시간) 별로 탐색하고, 그 시간에 맞는 동생 위치를 이전에 방문했는지 찾는 방법이다.

두 방식 모두 2차원 방문 배열을 사용했다. 짝수, 홀수를 나누기 위해서다. 

예를 들어서, 3초에 5번위치를 방문했다면 +1, -1을 이용해서 3초, 5초, 7초, 9초,... 에 5번 위치에 올 수 있다. 따라서 홀수에 어떤 위치를 방문했다면 그 이후 모든 홀수번째 시간에는 그 위치를 다시 방문해 봤자 최소시간이 아니라는 뜻이다.

동생이 i초에 A위치에 방문할 예정이라면, 수빈이는 i초가 되기 전 언제든 그 위치에 미리 방문해서 기다리면 된다. 대신, 제자리에서 기다려야하기 때문에 꼭 짝수, 홀수는 맞아야 한다. (A+1-1=A)

 

1.  위치별 가능한 최소시간 전부 구하기

입력

2차원 방문배열에 홀수/짝수 시간대 별 해당 위치에 방문한 최초의 시간을 저장한다.

두 배열 모두 -1로 초기화하고, 첫 번째 위치 N (visited[0(짝수)][N])에 0초를 저장한다.

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 = 500000;

int[][] visited = new int[2][END + 1];
Arrays.fill(visited[0], -1);
Arrays.fill(visited[1], -1);
visited[0][N] = 0;

 

BFS

1.  위치와 시간이 저장된 int[]를 넣는 큐를 만든다. 

2.  초기 위치 N과 0초를 큐에 넣는다.

3.  큐가 빌 때까지 탐색한다.

3-1. queue의 맨 앞 int[]를 꺼내서 [0]은 now에, [1]은 1을 더해서 time에 저장한다. 이동 한 번마다 1초가 걸리기 때문이다.

3-2.  *2, +1, -1 에 도달할 수 있는지(0 이상 END 이하), 방문한 적 없는지 확인한다.

3-3.  방문배열은 time%2로 접근한다. 0이면 짝수, 1이면 홀수다. 앞에서 이미 time++했기 때문에 다른 연산은 필요 없다.

3-4.  방문 가능하다면 queue에 넣고 visited에 time을 저장한다.

4.  탐색이 완료되면 0부터 END위치까지 홀수, 짝수 시간 별 도달할 수 있는 최소 시간을 모두 구한 것이다.

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

int now, time;
while (!queue.isEmpty()) {
   now = queue.peek()[0];
   time = queue.poll()[1] + 1;

   if (now * 2 <= END && visited[time%2][now * 2] == -1) {
      queue.offer(new int[]{now * 2, time});
      visited[time%2][now * 2] = time;
   }
   if (now + 1 <= END && visited[time%2][now + 1] == -1) {
      queue.offer(new int[]{now + 1, time});
      visited[time%2][now + 1] = time;
   }
   if (now - 1 >= 0 && visited[time%2][now - 1] == -1) {
      queue.offer(new int[]{now - 1, time});
      visited[time%2][now - 1] = time;
   }
}

 

동생을 찾는 가장 빠른 시간 구하기

1.  동생을 찾을 수 없다면 -1을 출력해야 하므로 answer을 -1로 초기화한다.

2.  K+1+2+...+ i +... 하면서 그 위치에 저장된 시간이 i보다 작다면 수빈이가 그 위치에서 i초까지 기다리면 된다는 뜻이다. 바로 answer에 i를 저장하고 반복을 끝낸다.

3.  answer을 출력한다.

int answer = -1;
for(int k=K,i=0;k<=END;i++,k+=i){
   if(visited[i%2][k] != -1 && visited[i%2][k] <= i){
      answer = i;
      break;
   }
}

System.out.println(answer);

 

전체 코드

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

public class BOJ_17071_숨바꼭질5 {
   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 = 500000;

      int[][] visited = new int[2][END + 1];
      Arrays.fill(visited[0], -1);
      Arrays.fill(visited[1], -1);
      visited[0][N] = 0;

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

      int now, time;

      while (!queue.isEmpty()) {
         now = queue.peek()[0];
         time = queue.poll()[1] + 1;

         if (now * 2 <= END && visited[time%2][now * 2] == -1) {
            queue.offer(new int[]{now * 2, time});
            visited[time%2][now * 2] = time;
         }
         if (now + 1 <= END && visited[time%2][now + 1] == -1) {
            queue.offer(new int[]{now + 1, time});
            visited[time%2][now + 1] = time;
         }
         if (now - 1 >= 0 && visited[time%2][now - 1] == -1) {
            queue.offer(new int[]{now - 1, time});
            visited[time%2][now - 1] = time;
         }
      }

      int answer = -1;
      for(int k=K,i=0;k<=END;i++,k+=i){
         if(visited[i%2][k] != -1 && visited[i%2][k] <= i){
            answer = i;
            break;
         }
      }

      System.out.println(answer);
   }
}

 

2.  수빈이 이동 기준 풀이

입력

visited 방문배열 타입은 boolean이다. 시간별로 탐색하고 체크할 것이기 때문에 방문여부만 알면 되기 때문이다.

N위치, 0(짝수)에 true를 저장한다.

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 = 500000;

boolean[][] visited = new boolean[END + 1][2];
visited[N][0] = true;

 

BFS

이 문제의 BFS 탐색은 "범위, 동생 위치 방문확인 - 다음 depth 방문처리 및 queue에 추가"가 반복된다.

int now	queue에서 꺼낸 위치
int time	찾고 있는 시간대(queue에 새로 넣고 있는 시간대)
int mod	time을 2로 나눈 값. 연산을 여러 번 하지 않기 위해 만들었다.
int size	한 depth에 처음 접근했을 때 queue size. 다음 depth와 섞이지 않기 위해 꼭 필요하다.
int move	현재 시간이 time일 때 동생 위치

1.  depth(=time)으로 체크하는 방법이다. queue에서 같은 depth들을 모두 탐색한다. 

2.  반복문 가장 앞에 동생 위치(move)가 END 이상인지 확인해야 한다. visited배열을 move로 접근하기 때문에 ArrayIndexOutOfBounds 예외가 나지 않으려면 이 순서가 중요하다. END 이상이라면 -1을 출력하고 끝낸다.

3.  visited[동생위치][짝/홀]을 이전에 방문한 적 있다면 time을 출력하고 끝낸다. 반복문 초반에 이걸 체크하는 이유는 time=0인 경우를 쉽게 확인하기 위해서다.

4.  다음 depth 방문처리를 위해 size, time, mod, move를 새로 설정한다. 

4-1.  size는 현재 queue의 사이즈로 정한다. for 반복문을 사용해서 다음 depth와 섞이지 않도록 하는 데 필요하다.

4-2.  time은 1을 더한다. mod는 time%2한 값을 저장한다.

4-3.  move(동생 위치)는 현재의 move에 time을 더한다.

5.  size만큼 반복하면서 queue에서 요소를 꺼낸 후 다음 위치(*2,+1,-1)에 방문 가능할 경우 queue에 넣는다. 방문처리도 해야 한다.

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

int now, time = 0, mod = 0, size, move = K;
while (!queue.isEmpty()) {
   if(move > END){//꼭 이 위치여야 함.
      System.out.println(-1);
      return;
   }
   if(visited[move][mod]){
      System.out.println(time);
      return;
   }

   size = queue.size();
   time++;
   mod = time%2;
   move += time;

   for(int s=0;s<size;s++){
      now = queue.poll();

      if (now * 2 <= END && !visited[now * 2][mod]) {
         queue.offer(now * 2);
         visited[now * 2][mod] = true;
      }
      if (now + 1 <= END && !visited[now + 1][mod]) {
         queue.offer(now + 1);
         visited[now + 1][mod] = true;
      }
      if (now - 1 >= 0 && !visited[now - 1][mod]) {
         queue.offer(now - 1);
         visited[now - 1][mod] = true;
      }
   }

}

 

전체 코드

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

public class BOJ_17071_숨바꼭질5_2 {
   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 = 500000;

      boolean[][] visited = new boolean[END + 1][2];
      visited[N][0] = true;

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

      int now, time = 0, mod = 0, size, move = K;
      while (!queue.isEmpty()) {
         if(move > END){//꼭 이 위치여야 함.
            System.out.println(-1);
            return;
         }
         if(visited[move][mod]){
            System.out.println(time);
            return;
         }

         size = queue.size();
         time++;
         mod = time%2;
         move += time;

         for(int s=0;s<size;s++){
            now = queue.poll();

            if (now * 2 <= END && !visited[now * 2][mod]) {
               queue.offer(now * 2);
               visited[now * 2][mod] = true;
            }
            if (now + 1 <= END && !visited[now + 1][mod]) {
               queue.offer(now + 1);
               visited[now + 1][mod] = true;
            }
            if (now - 1 >= 0 && !visited[now - 1][mod]) {
               queue.offer(now - 1);
               visited[now - 1][mod] = true;
            }
         }

      }

   }
}

---

3. 결과

홀/짝 구분하는 아이디어가 떠오르지 않아서 여기저기 많이 찾아봤다.