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

풀이 아이디어

BFS + DP

BFS인 이유는 그래프 탐색처럼 0초부터 쭉 탐색하고 이후 1초, 2초,...를
탐색하기 때문이고
DP라고 생각한 이유는 최소 시간을 cases 배열로 가능한 경우의 수를
계속 갱신해주기 때문이다.

시간 순을 기준으로 가장 짧은 시간으로 탐색할 수 있는 곳부터 탐색한다.

• boolean[] visited = new boolean[100001]; // 위치로 방문 여부
• int[] times = new int[100_001]; // 위치로 방문시 지난 시간
• int[] cases = new int[100_001]; // 위치로 갈 수 있는 경우의 수
• int minFindTime = Integer.MAX_VALUE; // 최소 시간
• int minFindCases = 0; // 최소 시간으로 찾는 경우의 수

현재 위치한 좌표와 시간을 저장하는 객체 Position을 큐에 넣어서 BFS로
탐색을 하는데 visited로 이미 방문했던 곳은 다시 큐로 넣지는 않지만
다른 곳에서 해당 위치로 더 빠른 시간에 방문할 수 있다면 '시간'과 '경우의 수'를 갱신해주고
다른 곳에서 해당 위치로 같은 시간에 방문할 수 있다면 '경우의 수'를 갱신해준다.

풀이 코드

import java.util.*;
import java.io.*;
class _12851{
    static class Position{
        int position;
        int time;
        Position(int position, int time){
            this.position = position;
            this.time = time;
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]); // 출발 위치
        int K = Integer.parseInt(input[1]); // 도착 위치
        
        boolean[] visited = new boolean[100001]; // 그 장소에 갔는지 여부
        int[] times = new int[100_001]; // 그 장소에 갔을 때 발생하는 시간
        int[] cases = new int[100_001]; // 그 장소에 갔을 때 발생하는 경우의 수

        int minFindTime = Integer.MAX_VALUE; // 최소 시간
        int minFindCases = 0; // 최소 시간으로 찾는 경우의 수

        Queue<Position> q = new LinkedList<>();
        q.add(new Position(N, 0));
        visited[N] = true;
        cases[N] = 1;
        
        while(!q.isEmpty()){
            // 큐에서 현재 위치를 뽑는다.
            Position currentNode = q.poll();
            int curPos = currentNode.position;
            int curTime = currentNode.time;

            // 현재 위치가 K와 같다면
            if(curPos == K){
                if(minFindTime > curTime){
                    minFindTime = curTime;
                    minFindCases = cases[curPos];
                }
                else if(minFindTime == curTime){
                    minFindCases += cases[curPos];
                }
                continue;
            }

            // 위치가 X일 때 1초 후에 X-1, X+1, 2*X로 이동할 수 있다.
            // 1초 뒤에 갈 수 있는 위치에 대해 큐에 넣는다.
            if(curPos-1 >= 0){
                if(visited[curPos-1]==false){
                    q.add(new Position(curPos-1, curTime+1));
                    visited[curPos-1] = true;
                    times[curPos-1] = curTime+1;
                    cases[curPos-1] += cases[curPos];   
                }
                // 이미 방문했지만 더 빠른 시간에 방문할 수 있다면 갱신
                else if(times[curPos-1] > curTime+1){
                    times[curPos-1] = curTime+1;
                    cases[curPos-1] = cases[curPos];
                }
                // 이미 방문했지만 같은 시간에 방문할 수 있다면 경우의 수를 더한다.
                else if(times[curPos-1] == curTime+1){
                    cases[curPos-1] += cases[curPos];
                }
            }
            if(curPos+1 <= 100000){
                if(visited[curPos+1]==false){
                    q.add(new Position(curPos+1, curTime+1));
                    visited[curPos+1] = true;
                    times[curPos+1] = curTime+1;
                    cases[curPos+1] += cases[curPos];
                }
                // 이미 방문했지만 더 빠른 시간에 방문할 수 있다면 갱신
                else if(times[curPos+1] > curTime+1){
                    times[curPos+1] = curTime+1;
                    cases[curPos+1] = cases[curPos];
                }
                // 이미 방문했지만 같은 시간에 방문할 수 있다면 경우의 수를 더한다.
                else if(times[curPos+1] == curTime+1){
                    cases[curPos+1] += cases[curPos];
                }
            }
            if(curPos*2 <= 100000){
                if(visited[curPos*2]==false){
                    q.add(new Position(curPos*2, curTime+1));
                    visited[curPos*2] = true;
                    times[curPos*2] = curTime+1;
                    cases[curPos*2] += cases[curPos];
                }
                // 이미 방문했지만 더 빠른 시간에 방문할 수 있다면 갱신
                else if(times[curPos*2] > curTime+1){
                    times[curPos*2] = curTime+1;
                    cases[curPos*2] = cases[curPos];
                }
                // 이미 방문했지만 같은 시간에 방문할 수 있다면 경우의 수를 더한다.
                else if(times[curPos*2] == curTime+1){
                    cases[curPos*2] += cases[curPos];
                }
            }
        }
        // 결과 출력 
        System.out.println(minFindTime);
        System.out.println(minFindCases);
    }
}