[백준]13549번 숨바꼭질3

(1:20)

13549번: 숨바꼭질 3

• 수빈이의 현재 점 : N (수평선)
• 동생이 위치하는 점 : K (수평선)
• 수빈이는 걷거나 순간이동 할 수 있다.
• 수빈이의 위치가 X일 때
  • 걷는다면, "1초" 후 x-1 또는 x+1로 이동하게 된다.
  • 순간이동을 한다면 "0초" 후, 2*x의 위치로 이동하게 된다.
• 수빈이와 동생의 위치가 주어졌을 때, [ 수빈이가 동생을 찾을 수 있는 가장 빠른 시간 ] ?

풀이 생각 : 이분탐색 + BFS?

• 이문제를 보고는 이분탐색법이 떠올랐다.

• 제한 시간을 이분탐색으로 정한 후, 해당 시간 이내에 수빈이가 동생을 찾을 수 있는지를 탐색하는 방식을 떠올렸다.

• 이분탐색에서 최대 시간은, |N-K| 를 한다.

• 각 경우에서 수빈이가 움직일 수 있는 방향은 세 가지가 있다.

  1. x-1 (1sec)

  2. x+1 (1sec)

  3. 2*x (0sec)

     이것에 대해서는 완전탐색을 수행해야만 한다. 2*x 로 K보다 멀리 가서 -1을 하는게 더 빠를 수 있기 때문에, 이런 경우를 위해서는 결국 완전탐색이 어느정도 필요하다.

     여기서 시간을 줄이기 위해서 이분탐색을 사용하는 경우가 많다.

  • 이분탐색으로 설정한 target time → t 라고 하자
  • 아직 k에 도달하지 않았는데, curT가 t보다 커진다면 해당 path는 실패다

• 문제는 풀리는데 굳이 Binary Search를 할 필요가 없었다.

그냥 BFS를 해도 됐다 → 이게 더 빠를 수 밖에 없다

• 오히려 Binary Search를 하려다 보니, 중복되는 problem을 또 다시 풀게 되었다.
• BFS를 할 때 주의할 점은 visit 을 check하는 시점이다.
  • 이 문제는 2x N 일 때는 0초를 더하기 때문에 무조건 depth가 낮다고 해서, 최소의 시간이 아니다.
  • 따라서 해당 N 위치에 대해 Queue에 먼저 들어간 것이 있더라도, 나중에 들어가는 것의 시간이 더 적을 수 있다.
  • 이런 점에서 BFS가 아닌 Disktra를 사용해도 될 것 같긴 하다. 일단 BFS 풀이를 하자.
• 그리고 이 문제는 +1 과 x2 이동 외에는 뒤로 이동하는 것은 -1 하나밖에 없다.
  • 따라서 k < n 인 경우에는 "-1"만을 사용하여 도달할 수 있다.

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

/*
* 1 10
* 1+ 1 = 2 -> 4 -> 8
* 1 2 4 8 -> 9, 10
*
*
* */
public class Main{
    public static int n,k;
    public static int max;
    public static int[] visit = new int[100001];
    public static int min = Integer.MAX_VALUE; // 최소 시간 (구하고자 하는 것 )
    public static void Setting() 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());
        max = Math.abs(n-k); // 최대 시간 -> 1초씩 이동하기
    }

    // 이 문제는 그냥 BFS를 해도 되는 문제였다.
    public static void solve(){
        if ( k<=n){
            min = Math.abs(n-k);
            return;
        }
        Arrays.fill(visit,Integer.MAX_VALUE);
        // bfs를 사용
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{n,0});
        int[] loop = new int[]{0,1,-1};
        // 수빈이의 위치에서 시작 한다
        // { 위치, 시간 }
        int next =0;
        int nextTime =0;
        int addTime =0;
        while(q.isEmpty()==false) {
            int[] cur = q.poll();
            // 이미 더 "적은 시간"으로 들어온게 있으면 pass
            if(visit[cur[0]]<cur[1]) continue;
 //           System.out.println("CURRENT : "+cur[0]+", time : "+cur[1]);
            loop[0] = cur[0]; // x2 할 곳
            for(int idx=0;idx<loop.length;idx++){
                if(idx>0) addTime=1;
                else addTime=0;
                // 다음 방문할 위치
                next = cur[0]+loop[idx];
                // next를 방문할 때 걸리는 시간
                nextTime = cur[1]+addTime;
                // k를 찾은 경우 -> update한다.
                if(next == k ){
                    if(min>nextTime)min = nextTime;
                    continue;
                }
                // 현재까지 k를 찾는데 걸린 시간보다 더 오랜 시간이 걸리면
                if(nextTime>=min) continue;
                // 범위를 넘는 경우 -> pass
                if(next<0 || next >100000) continue;
                // 이미 더 적거나 같은 시간으로 방문한 적 있는지
                if(visit[next]<=nextTime) continue;
                // 이곳을 방문하는데 이게 더 짧은 시간
                visit[next]= nextTime;
                q.add(new int[]{next, nextTime});
            }
        }

    }
 
    
    public static void main(String[] args) throws IOException {
        Setting();
        solve();
        System.out.println(min);

    }
}