숨바꼭질(1697)

숨바꼭질(1697)

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

public class Main{
    
  static int[] cnt = new int[100001];
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
    
    Arrays.fill(cnt, -1);
    
    count(n, k);
    
    sb.append(cnt[k]);
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static void count(int n, int k){
    Deque<Integer> dq = new ArrayDeque<>();
    
    dq.offerFirst(n);
    cnt[n] = 0;
    
    while(!dq.isEmpty()){
      int num = dq.pollLast();
      
      if(cnt[k] != -1) break;
      
      if(num-1 >= 0 && cnt[num-1] == -1){
        cnt[num-1] = cnt[num] + 1;
        dq.offerFirst(num-1);
      }

      if(num+1 <= 100000 && cnt[num+1] == -1){
        cnt[num+1] = cnt[num] + 1;
        dq.offerFirst(num+1);
      }
      
      if(num*2 <= 100000 && cnt[num*2] == -1){
        cnt[num*2] = cnt[num] + 1;
        dq.offerFirst(num*2);
      }
    }
  }
}

풀이과정

1. BFS로 풀면 될거라고 생각을 했다.
2. 근데 막상 구현을 할 때, que를 사용하지 않고, for문을 이용해 순차적으로 접근하여 값을 넣는다는 생각을 하게 되었다.
3. 처음 생각은 n에 대해서 -1, +1, *2 에 해당하는 배열의 값에 +1씩 증가시키는 거였다.
   1) arr[5]=0, arr[4]=1, arr[6]=1, arr[10]=1
   2) 여기서 꼬리를 물어서
   3) 4와 연결된, arr[3]=2, arr[8]=2
   4) 3과 연결된, arr[2]=3. arr[6]=3이지만 arr[6]이 이미 1이므로 결론은 arr[6]=1
   5) 2와 연결된, arr[1]=4, arr[4]=4이지만 arr[4]가 이미 1이므로 결론은 arr[4]=1
4. 이렇게 접근을 하다보니 n의 밑으로 내려갈 때, 그리고 올라갈 때를 생각하게 되었고,
5. 올라갈 때를 생각하다보니, 무한루프에 빠지게 되었다.
   1) 6과 연관된, arr[7]=2, arr[12]=2
   2) 7과 연관된, arr[8]=3 근데 arr[8]에는 이미 2가 있으므로, arr[8]=2, arr[14]=3
   3) 8과 연관된, arr[9]=4, arr[16]=4
   4) 이렇게 접근을 하다보니 arr[9]의 경우는 5-10-9 로 접근을 하는것이 더 빠른데 잘못된 값이 입력이 되는거였다.
6. 저기서 arr[9]와 같은 경우를 생각하다보니, arr[n]의 값을 arr[n-1]+1 , arr[n+1]+1, n이 짝수면 arr[n/2]+1
7. 이런식으로 생각하다보니 경우의 수가 많아지고 분기 처리가 복잡하게 되었다.
8. 모든 구현식을 초기화 시키고, 다시 BFS의 원리를 생각하며, que를 이용하여 풀었다.

- 성공
- 메모리 : 16132 KB
- 시간 : 164 ms

보안점

1. 표를 이용하여 시간의 흐름에 따라 제거해가며 풀면 조금 더 정리가 되고 이해가 잘 되는 것 같다.
2. 0초일 때는 5에 위치,
3. 1초 후에는 4, 6, 10에 위치
4. 2초 후에는 3, 8, 7, 12, 9, 20에 위치
5. 3초 후에는 2, 16, 14, 11, 13, 24, 18, 19, 21, 40
6. 이런식으로 표를 이용해서 칸을 채워가면 로직을 더 쉽게 이해할 수 있을 것 같다.
7. 알고리즘의 풀이에 있어서 시각화 도구를 잘 사용하는 연습을 해야겠다.