백준 12851번 : 숨바꼭질 2 java

이 문제는 가장 빠른 시간으로 동생을 찾을 수 있는 시간과 이렇게 찾는 방법이 몇 가지인지를 찾는 문제입니다.

이 문제를 풀 때 유의하셔야 하는 점은 중복을 허용해주어야 한다는 것입니다.

5에서 17로 갈 때는 아래와 같이 중복이 없을 수도 있습니다.

하지만 1에서 4로 갈 때를 살펴보겠습니다.

다음과 같이 같은 칸으로 같이 시간이 걸려서 갈 때도 있기 때문에 중복을 허용해 주어야 합니다.

따라서 우리는 중복을 허용해주면서 더 이상 queue에 값을 넣지 않는 상황을 설정해주어야 합니다.

중복을 허용해 주지 않는 상황들을 아래에 나열하도록 하겠습니다.

1. 도착 지점의 시간값이 지금 노드의 시간 값보다 작을 때

bfs를 사용하여 위 문제를 풀 때 모든 간선의 가중치가 같기 때문에 다음 노드로 나아갈 때 시간이 줄어들지 않습니다.

따라서 도착 지점의 시간값이 현재 노드의 시간 값보다 작을 때 이 노드는 queue에 추가하지 않아도 됩니다.

 

2. 다음 노드의 좌표가 0보다 작거나 100,000보다 클 때

이 문제에서 '수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다.'는 조건이 있습니다.

따라서 이 구간을 넘어가면 queue에 추가하지 않습니다.

 

이러한 것들을 조심하면서 문제를 풀어보았습니다.

---

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

public class Main {
    static int K;
    static int min = Integer.MAX_VALUE;
    static int count = 0;
    static int[] time = new int[100_001];

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        //수빈이가 앞에 있을 때 처리
        if (N >= K) {
            System.out.println((N-K) + "\n1");
            return;
        }


        bfs(N);

        System.out.println(min);
        System.out.println(count);
    }

    static void bfs(int start){
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        time[start] = 1;

        while(!q.isEmpty()){
            int now = q.poll();

            //min이 생성되었다면 bfs이므로 동생에게 가는 시간의 최솟값이 정해졌으므로
            //min의 시간보다 now의 좌표에서 시간이 더 오래걸리면 비교할 필요가 없음
            if(min<time[now])
                continue;

            for(int i =0; i<3; i++){
                int next;

                if(i == 0)
                    next = now*2;
                else if(i == 1)
                    next = now+1;
                else
                    next = now-1;

                //범위를 넘어가면 continue
                if(next<0 || next>100_000)
                    continue;

                if(next == K){
                    min = time[now];
                    count++;
                }

                //next에 처음 들어가면 offer해주고 next가 now보다 1시간이 더 걸리면
                //경우의 수가 추가될 수도 있으니 offer
                if(time[next] == 0 || time[next] == time[now] + 1){
                    q.offer(next);
                    time[next] = time[now] + 1;
                }
            }
        }
    }
}

위에서 말씀드린 것들을 조심하면서 풀었고

//next에 처음 들어가면 offer해주고 next가 now보다 1시간이 더 걸리면
//경우의 수가 추가될 수도 있으니 offer
if(time[next] == 0 || time[next] == time[now] + 1){
    q.offer(next);
    time[next] = time[now] + 1;
}

이 코드 부분은 처음 검사하는 구간은 추가를 해주니다.

if문 의 || 뒤의 조건이 당연한 것이 아니냐하실 수도 있지만 time[next] <= time[now]의 경우는 next를 거쳐갔을 때 이전 갔던 방법보다 빠르게 갈 수 없기 때문에 제외해주기 위해서 저러한 조건을 추가하였습니다.

이러한 조건은 위에서 말씀드린 1번 조건에 대한 구현입니다.