[Java] 백준 13549번 : 숨바꼭질 3

1. 문제

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

13549번: 숨바꼭질 3

 

 

2. 풀이 과정

[방법1] PriorityQueue를 이용한 BFS

도착 지점이 출발 지점보다 작은 경우, 빼기만 해서 가는 것이 가장 빠르므로 N-K를 출력한다.

아닌 경우는 PriorityQueue를 써서, 현재 최소 경로인 값에 +1, -1, *2 를 해본다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int K = Integer.parseInt(inputs[1]);
        
        if(K <= N){
            System.out.println(N-K);
        }
        else{
            boolean[] visited = new boolean[100_001];
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);
            pq.add(new int[]{N, 0});

             while(!pq.isEmpty()){
                int[] now = pq.poll();
                if(now[0] == K){
                    System.out.println(now[1]);
                    break;
                }
             
                visited[now[0]] = true;

                if(now[0] - 1 >= 0 && !visited[now[0] - 1]){
                    pq.add(new int[]{now[0] - 1, now[1] + 1});
                }
                if(now[0] + 1 <= 100000 && !visited[now[0] + 1]){
                    pq.add(new int[]{now[0] + 1, now[1] + 1});
                }
                if(now[0] * 2 <= 100000 && !visited[now[0]*2]){
                    pq.add(new int[]{now[0]*2, now[1]});
                }
            }
        }
        
    }
}

 

결과

 

[방법2] DP

짝수면, 자기 앞에서 +1해서 올 경우와 *2해서 올 경우만 고려하면 된다. 자기 바로 뒤의 값은 홀수이기 때문이다.

짝수가 아닐 경우, 자기 앞에서 +1해서 올 경우와 자기 뒤에서 -1해서 올 경우 2가지 중 최소를 구하면 된다.

i+1번째 수는 dp[i]+1이나 dp[(i+1)/2] 중에 최소를 고려하므로 i번째에서는 전자보다는 무조건 작을 것이므로 후자만 고려해주면 된다. 따라서 식은 Math.min(dp[i-1] + 1, dp[(i+1)/2] + 1)이 된다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        int N = Integer.parseInt(inputs[0]);
        int K = Integer.parseInt(inputs[1]);
        int[] dp = new int[K+1];

        if(K <= N){
            System.out.println(N-K);
        }
        else{
            for(int i=0; i<N; i++){
                dp[i] = N-i;
            }
            for(int i=N+1; i<=K; i++){
                if(i%2==0){
                    dp[i] = Math.min(dp[i/2], dp[i-1] + 1);
                }
                else{
                    dp[i] = Math.min(dp[i-1] + 1, dp[(i+1)/2] + 1);
                }

            }
            System.out.println(dp[K]);
        }

    }
}

 

결과