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

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

걷기와 순간이동을 이동해 I -> J로 가는 최단 시간과 최단 시간 내 갈 수 있는 경로의 개수를 구하는 문제이다.

BFS를 통해서 최단 시간을 구하는 것은 쉬우나, 최단 경로의 개수를 구하는 부분이 조금 헷갈렸다.

결국 내린 결론은 기존 BFS를 유지하되, BFS로 처음 도달한 최단경로의 시간을 저장해놓고, 해당 시간 위로 넘어가는 케이스를 전부 자르고, 목표지점의 방문체크를 하지 않는 방법으로 Count를 증가시켜 풀었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Predicate;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        int[] arr = Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
        int st = arr[0];
        int fi = arr[1];
        int depth = Integer.MAX_VALUE;
        Loca start = new Loca(st,0);
        Queue<Loca> q = new LinkedList<>();
        q.offer(start);
        int count = 0;
        boolean[] visited = new boolean[100001];
        while(!q.isEmpty()){
            Loca target = q.poll();
            int v = target.v;
            int d = target.d;
            if(d>depth) continue;
            if(v==fi){
                depth = d;
                count++;
                continue;
            }
            visited[v] = true;
            if(check(v+1,visited,depth,d)) q.offer(new Loca(v+1,d+1));
            if(check(v-1,visited,depth,d)) q.offer(new Loca(v-1,d+1));
            if(check(v*2,visited,depth,d)) q.offer(new Loca(v*2,d+1));
        }
        System.out.println(depth);
        System.out.println(count);
    }

    public static boolean check(int v, boolean[] visited, int maxDepth, int depth){
        Predicate<Integer> value = i-> i<0||i>=visited.length||visited[i];
        Predicate<Integer> dept = i -> i<=maxDepth;
        return value.negate().test(v)||dept.negate().test(depth);
    }
}

class Loca{
    int v;
    int d = 0;
    Loca(int v, int d){
        this.v = v;
        this.d = d;
    }
}