[BOJ] 1697 숨바꼭질 - JAVA

1. 문제

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

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

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

 

N<K인 경우, N==K인 경우, N>K인 경우가 모두 있다는 걸 기억해야한다.

---

2. 풀이

나머지는 bfs방식과 흡사한데, "//이 부분"이라고 주석 친 부분만 짚어본다.

1) Math.max(k<<1,n)+1

이동은 최대 k*2만큼만 갈 수 있다. 그 이상은 필요가 없다. 예를 들자면, 99에서 197로 가는 최소값은 99*2-1=> 총 두 번이다.

그런데 여기서 꼭 알아두어야 할 점은, n이 k보다 클 수도 있다는 점이다. 특히 n이 k의 두 배 이상 큰 경우도 있을 수 있다. 10->2를 가야할 때, k<<1로만 사이즈를 정한다면 항상 카운트 배열의 인덱스를 넘게 된다.

2) 카운트 배열을 -1이나 Integer.MAX_VALUE값으로 초기화하지 않기 위해 counts[n]을 1로 설정했다. 방문체크를 할 때 0보다 큰지만 체크하기 위함이다. 그래서 마지막에 리턴할 때 counts[k]-1을 해주었다.(경과한 시간을 구하고 있으니까)

3) PriorityQueue가 아니다. 그냥 Queue다. 이 이유와 내가 겪은 시행착오들은 3. 결과에 자세하게 써보았다.

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

public class BOJ_1697_숨바꼭질 {
   public static void main(String[] args) throws IOException {
      StringTokenizer st = new StringTokenizer(new BufferedReader(new InputStreamReader(System.in)).readLine());
      System.out.println(find(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
   }

   private static int find(int n, int k) {
      int size = Math.max(k << 1, n) + 1;    //이부분
      int[] counts = new int[size];
      counts[n] = 1;	//이부분

      Queue<Integer> queue = new LinkedList<>(); //이부분
      queue.offer(n);

      while (!queue.isEmpty()) {
         n = queue.poll();
         if (n == k) break;

         int[] next = {n + 1, n - 1, n * 2};
         for (int nn : next) {
            if (nn < 0 || nn >= size || counts[nn] > 0) continue;
            counts[nn] = counts[n] + 1;
            queue.offer(nn);
         }
      }

      return counts[k] - 1;
   }
}

---

3. 결과

스택오버플로우는 dfs쓰다가 났고, 중간의 인덱스 에러는 범위 체크를 잘못해서, 마지막 인덱스 에러들은 N>K인 경우를 생각 못해서 틀렸다.

 

첫번째로 맞은 경우는 좀 더럽게 짠 코드다. n+1, n-1, n*2 다 따로 해서 범위체크도 각각했다. 그래서 메모리나 시간은 제일 짧지만 가독성이 별로라서 좀 고쳤다.

두번째로 맞은 경우는 next를 사용하기 시작한 코드인데, 갑자기 시간이 늘어나서 static이 문제인가 하고 고민했다.

그래서 세번째로 제출한 코드는 static 없이 지역변수로 n,k를 넣었다. 하지만 시간이 더 늘어났다.ㅎㅎ

네번째는 혹시나 싶어서 큐 반복문 안에 있는 n을 지역변수 n 이름으로 덮어씌워줘봤다. 아주 조금 시간이 감소했다.

next 배열을 쓰고 메모리가 차이나는 건 어쩔 수 없다. 어쨌든 하나를 더 만들어서 저장했으니까.

 

제출은 하지 않았지만 틀린 경우가 또 있었는데, 처음에 다익스트라 방식으로 하려고 priority queue에 int[] 값을 집어넣고 카운트가 적은 순서대로 줄세운 방식이다. 하지만 애초에 카운트는 +1씩만 되기 때문에 최소값인지 계산하기 위해 여러번 방문할 필요가 없다. 가장 처음 방문했을 때가 최소값이기 때문이다. 이건 정확히 말하면 안되는 방식은 아니지만 쉬운 길을 굳이 어렵게 돌아가는 방식이라고 할 수 있다.

 

두번째로 priority queue를 쓰긴 쓰는데 k와 절대값 차이가 작은 순으로 정렬해서 인덱스만 저장하는 방식을 시도해봤다. 하지만 이것도 안된다. 그런식으로 하려면 인덱스와 그때의 카운트를 같이 저장해주어야한다. 굳이 이런 식으로 할 필요 없을 것 같아서 하지 않았다. 더 복잡해지기만 하지...  

 

priority queue를 사용하면 우선순위대로 정렬을 알아서 하기 때문에 넣은 순서가 깨진다. 이 의미는, 가장 가까운 순으로 방문하지 않는다는 소리다. int[]를 사용해서 그 때의 cnt값을 저장한다고 한들, 순서대로 방문하지 않았기 때문에 언제든 그 cnt값보다 작은 cnt가 나올 수 있어 여러 번 방문해야 한다.