13549번 숨바꼭질 3

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

public class HideAndSeek3 {
    static int N;
    static int K;
    static int[] dir = {-1,1};
    static boolean[] visited;

    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());
        visited = new boolean[100001];
        bfs();
    }
    public static void bfs(){
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{N,0});
        visited[N] = true;
        while (!que.isEmpty()){
            int[] current = que.poll();
            int place = current[0];
            int time = current[1];
            if(2*place<100001&&!visited[2*place]){
                visited[2*place] = true;
                que.add(new int[]{2*place,time});
            }
            for (int i = 0; i < 2; i++) {
                int next = place+dir[i];
                if(next>=0&&next<100001&&!visited[next]){
                    visited[next] = true;
                    que.add(new int[]{next,time+1});
                }
            }
            if(place==K){
                System.out.println(time);
                return;
            }

        }
    }

}

풀이방법

현재 위치x에서 갈 수 있는 방법은 총 세가지가 있다.
x-1,x+1,2*x

1. 방문하지 않은 곳이라면 큐에 넣어준다.
2. 큐에 넣을때, 위치와 시간을 함께넣는데, 2*x로 이동할때는 시간을 추가하지 않는다.
3. 현재 위치가 K라면 그때의 시간을 출력한다.

📢간단한 bfs이지만 주의해야 할 점이 있다.
K로 이동하는 경우의 수가 한가지가 아니므로 최소값을 찾아야 하는데,
해당 문제는 2x로 이동할때 시간추가가 되지 않으므로, 큐에 2x로 이동하는 경우를 항상 먼저 넣어야 한다.

후기

이문제는 풀이방법이 두가지 있다.
1. bfs탐색
2. 다익스트라 탐색

나는 1번으로 풀었다. 2*x로 이동할때가 무조건 최소인 문제라 다행히 1번으로 풀 수 있었지만, 변수가 조금만 더 추가 되면, 2번으로만 풀어야할 것 같다.

매번 최솟값을 저장하면서 다음 노드를 탐색하는 다익스트라는 dp유형과 비슷한것 같다.