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

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

 

1. 문제 설명

 

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

 

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

 

2. 풀이

 

BFS로 풀 수 있는 문제이다. BFS로 위치들을 방문해가면서 현재 위치 X에서 다음 위치로 가능한 위치들(X+1, X-1, X*2)들이 이전에 방문했는지 확인하고 방문하지 않았다면 현재 위치까지의 최소 시간 +1을 다음 위치의 최소 시간으로 저장한다.

 

이전 방문을 확인하지 않으면 메모리 초과 또는 시간 초과가 날 수 있다.

 

그런데 수빈이의 위치가 동생의 위치보다 더 큰 경우에는 1씩 감소해나가면서 이동하는 게 최솟값이다.

수빈이의 위치와 동생의 위치를 비교하여 수빈이가 동생보다 위치가 작은 경우에만 BFS로 풀었다.

 

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();

        

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

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

            location.add(N);

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

            while(!location.isEmpty()) {

                int now = location.poll();

                if(now==K)
                    break;

                if (now - 1 >= 0 && dp[now - 1] == 0) {
                    dp[now - 1] = dp[now] + 1;
                    location.add(now - 1);
                }

                if (now + 1 <= K && dp[now + 1] == 0) {
                    dp[now + 1] = dp[now] + 1;
                    location.add(now + 1);
                }

                if (now * 2 < K * 2 && dp[now * 2] == 0) {
                    dp[now * 2] = dp[now] + 1;
                    location.add(now * 2);
                }
            }

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



    }





}