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

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

 

1. 문제 설명

 

수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간을 출력하는 문제이다.

 

수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1 위치로 이동하고 0초 후에 X*2 위치로 이동할 수 있다.

 

 

2. 풀이

 

kwoncorin.tistory.com/70

[JAVA]백준 1697번: 숨바꼭질

백준 1697번 숨바꼭질 심화 문제이다.

 

1697번에서는 1초 후에 X*2 위치로 이동하였지만 이번 문제에서는 0초 후에 X*2 위치로 이동하는 것으로 변경되었다.

 

1697번은 X+1, X-1, X*2 중 어떤 방식으로 이동하여도 현재 시간에서 1씩 증가하였기에 방문 여부를 DP 배열이 0인지 아닌지로 구분할 수 있었다.

 

하지만 이번 문제는 X*2 위치로 이동할 때 시간이 증가하지 않기에 같은 방식으로 구분할 수 없다.

 

따라서 VISITED 배열을 따로 사용하여 현재 위치를 이전에 방문하였는지를 판단하였다.

 

현재 위치에서 다음 위치로 이동할 때 다음 위치를 이미 방문하였다면 다음 위치의 최소 방문 시간보다 현재 위치에서 이동하는 것이 더 최소 시간 이거나 아니면 방문하지 않았을 경우에만

 

다음 위치를 큐에 넣어서 확인한다.

 

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {



    public static void main(String[] args) {

        Scanner scan=new Scanner(System.in);

        int N=scan.nextInt();
        int K=scan.nextInt();
        boolean flag=true;




        if(N>=K)
            System.out.println(N-K);
        else{

            Queue<Integer> location=new LinkedList<>();

            location.add(N);

            int dp[]=new int[K*2+1];
            boolean visited[]=new boolean[K*2+1];

            visited[N]=true;


            while(!location.isEmpty()) {

                int now = location.poll();

                if(now==K)
                    break;

                if (now - 1 >= 0) {
                    if (dp[now - 1] > dp[now] + 1 || !visited[now - 1]) {
                        visited[now - 1] = true;
                        dp[now - 1] = dp[now] + 1;
                        location.add(now - 1);
                    }
                }

                if (now + 1 <= K) {
                    if (dp[now + 1] > dp[now] + 1 || !visited[now + 1]) {
                        visited[now + 1] = true;
                        dp[now + 1] = dp[now] + 1;
                        location.add(now + 1);
                    }
                }

                if (now * 2 < K * 2) {
                    if (dp[now * 2] > dp[now] || !visited[now * 2]) {
                        visited[now * 2] = true;
                        dp[now * 2] = dp[now];
                        location.add(now * 2);
                    }
                }


            }

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



    }


}