[백준 12851] 숨바꼭질 2 - JAVA

BOJ Link

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

 

풀이 과정

N에서 N-1, N+1, N*2 각각의 경우를 탐색하여, K에 도달하는 최소 depth와, 경우의 수를 출력하는 완탐 + 그래프 탐색 문제이다.

 

방문 체크 배열에 depth를 기록한다. 탐색 순서에 따라 똑같은 값에 도달하더라도, depth가 더 작은 경우가 있을 수 있다. 이를 체크하기 위함이다. (또한 N+1 => N-1 => N+1 => N-1 무한 루프를 막는다.)

 

똑같은 값에 도달할 때, depth가 같더라도 탐색한다. 정답에서 최소 depth와 함께 "경우의 수"도 요구하기 때문이다. depth만 요구한다면, 방문 체크 배열보다 depth가 작을때만 탐색해도 된다.

 

굳이 최적화 하자면, 같은 값이고 depth가 작을때, 값이 K이고 depth 이하일 때 탐색(혹은 정답 갱신하고 탐색x)한다.

 

마지막으로 N+1, N-1, N*2 별로 경계 체크를 진행하면 된다.

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    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());
        int K = Integer.parseInt(st.nextToken());
        int MAX = 100000;
        int ans = Integer.MAX_VALUE;
        int ansCnt = 0;

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{N, 0});

        int[] visited = new int[MAX + 1];
        Arrays.fill(visited, Integer.MAX_VALUE);
        visited[N] = 0;

        while (!q.isEmpty()) {
            int[] info = q.poll();
            int val = info[0];
            int dep = info[1];

            if (val == K) {
                if (dep == ans) ansCnt++;
                else {
                    ans = dep;
                    ansCnt = 1;
                }
                continue;
            }

            int nextDep = dep + 1;
            int mul = val * 2;
            int plus = val + 1;
            int minus = val - 1;

            if (mul <= MAX && nextDep <= ans && visited[mul] >= nextDep) {
                q.offer(new int[]{mul, nextDep});
                visited[mul] = nextDep;
            }
            if (plus <= MAX && nextDep <= ans && visited[plus] >= nextDep) {
                q.offer(new int[]{plus, nextDep});
                visited[plus] = nextDep;
            }
            if (minus >= 0 && nextDep <= ans && visited[minus] >= nextDep) {
                q.offer(new int[]{minus, nextDep});
                visited[minus] = nextDep;
            }
        }

        System.out.println(ans);
        System.out.println(ansCnt);
    }
}