[JAVA]백준 12851번: 숨바꼭질 2

www.acmicpc.net/problem/12851

12851번: 숨바꼭질 2

 

1. 문제 설명

 

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

 

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

 

 

2. 풀이

 

kwoncorin.tistory.com/70?category=939904

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

백준 1697번 숨바꼭질 문제 (동생을 찾을 수 있는 가장 빠른 시간)에 추가적으로 가장 빠른 시간으로 찾는 방법을 구하면 되는 문제이다.

 

1697번과 마찬가지로 수빈이가 동생보다 더 큰 위치에 있을 때는 한 가지 방법밖에 없으므로 최소 시간은 N-K초이고 최소 시간으로 찾는 방법은 한 가지이다.

 

동생이 더 큰 위치에 있을 때에는 dp 배열을 이용하여 답을 구하였다.

 

• dp [X][0] : X 위치까지 가는 가장 빠른 시간
• dp [X][1] :  X 위치까지 가는 가장 빠른 시간으로 찾는 방법의 가지 수

현재 위치 (now)에서 다음 위치로 가능한 곳을 next(now+1, now-1, now*2)라고 하자.

 

만약 dp [next][0]의 값이 0이라면 최초로 방문하는 것이기에 큐에 값을 저장한다.

 

next를 가는 가장 빠른 시간은 현재 위치까지 오는 가장 빠른 시간에 1을 더한 값이고 (dp [next][0]=dp [now][0]+1)

 

next를 가장 빠른 시간으로 찾는 방법의 수는 현재 위치까지 가장 빠른 시간으로 찾는 방법의 수를 더한 값과 같다. (dp [next][1]+=dp [now][1])

 

dp [next][0]의 값이 dp [now][0] 값에 1을 더한 값과 같다면 중복방문이므로 큐에 값을 저장하지는 않는다.

 

하지만 값이 같다는 것은 현재 위치 now에서 next로 이동하는 것도 가장 빠른 시간으로 이동할 수 있는 방법이기에

 

dp [next][1]의 값에 dp [now][1]을 더한다.

 

※ 중복방문 허용

 

아래의 코드는 중복방문을 하지 않는다. 

 

이미 방문한 적이 있는 위치의 경우 큐에 저장하지 않는다.

 

하지만 dp [next][0]==dp [now][0]+1인 next에 대해 중복방문을 하는 것으로 바꾼다면

 

dp [next][1]에 dp [now][1]의 값을 더하는 것이 아니라 

 

dp [next][1]에 1만 더해도 된다.

 

중복방문을 하는 경우 큐에는 현재 시간만큼 이동했을 때 최소 시간으로 방문이 가능한 위치들이 중복되어 저장된다.

 

위치 X를 최소 시간으로 방문하는 경우의 수가 3가지라면 큐에는 X가 3개 저장되어있다.

 

그렇기에 X를 3번방문하게 되고 최소 시간 방문 경우의 수를 1씩만 더해도 답을 구할 수 있는 것이다.

 

하지만 중복방문을 하지 않는 경우에는 X를 1번만 방문하기 때문에 다음 위치의 최소 시간 방문의 경우의 수는 1이 아닌 현재 위치의 최소 시간 방문의 경우의 수를 더해야 하는 것이다.

 

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+"\n1");
        else{

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

            location.add(N);

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

            dp[N][1]=1;

            while(!location.isEmpty()) {

                int now = location.poll();

                if(now==K)
                    break;

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


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

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


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

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

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


            }

            System.out.println(dp[K][0]+"\n"+dp[K][1]);
        }



    }





}

중복 방문 X

중복 방문 O