[백준] 1697 숨바꼭질 (JAVA)

풀이

 처음에 이 문제를 보고 어떠한 규칙을 찾기위해 노력을 했었다. 그러다 문득 바이너리 서치처럼 한번에 하나씩 하면 될것 같다는 생각이 들어 바이너리 서치로 접근을 해보았다. 그러나 바이너리 서치는 +1-1 *2중 무엇이 최적인지 몰랐고 그리디 알고리즘도 맞지 않았다. 그리하여 어떻게 하면 좋을까 생각을 하다 그냥 시간 생각하지말고 무작정 시간을 더하면 되지않을까? 라는 생각을 하게 되었고 그러한 생각을 꾸준히 하다보니 단순히 +1, -1, *2를 해서 특정배열에 담으면 될것 같다는 생각을 하게 되었고 이는 곧바로 정답으로 가게 되었다. 풀이의 발상은 단순하다 만약 현재의 위치가 x라면 x-1, x+1 x*2의 위치에 현재의 시간+1을 더하고 queue에 집어넣는것이다. 그러고 전부 끝나면 현재 queue에 있는 원소를 뽑아내어 반복을 한다. 그러다 현재의 위치와 K와 같아지면 거기서 멈추고 특정배열의 K값을 넣으면 이동하는데 걸리는 최소시간이 얻을수있다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main{
    public static Queue<Integer> queue = new LinkedList<Integer>();
    public static Integer [] arr = new Integer[1000001];
    public static int N, K;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        queue.offer(N);
        int idx = -1;
        arr[N] = 0;
        if (N == K) {
            System.out.println("0");
            return;
        }
        while(!queue.isEmpty()){
            idx = queue.poll();
            if((idx-1 >= 0) && (arr[idx-1]==null)){
                queue.offer(idx-1);
                arr[idx-1] = arr[idx]+1;
                if(idx-1 == K)
                    break;
            }
            if((idx +1 <1000001) && (arr[idx+1]==null)){
                queue.offer(idx+1);
                arr[idx+1] = arr[idx]+1;
                if(idx+1 == K)
                    break;
            }
            if((idx * 2 < 1000001) && (arr[idx*2] == null)){
                queue.offer(idx*2);
                arr[idx*2] = arr[idx]+1;
                if(idx*2 == K)
                    break;
            }
        }
        System.out.println(arr[idx]+1);
    }
}