[백준] 12851번 숨바꼭질 2

1) 생각

최단 시간을 찾아야하므로 BFS를 이용하여 각 n을 방문해보면서 이미 방문한 지점은 제외하고 k 지점에 도착하는 순간을 찾으면된다. 똑같은 숨바꼭질 문제가 여럿있고 다 비슷한 풀이 방식을 요구한다. 이문제의 경우 다른 점은 최소값 이외에도 최소값에 맞춰서 몇 번이나 도달할 수 있는가를 물어본다.

2) 방안

최소값만 찾으면 될 경우 break 문을 통해 바로 빠져나왔겠지만 그 숫자도 알아야하므로 BFS의 특징인 단계별로 나아간다는 점이 있으므로(뒤로, 앞으로, *2가 모두 +1 씩이므로) 일반적인 BFS 방식으로 풀수있다. 처음 도착하는 값이 최소 값이므로 그 값을 보관해두고 개수를 세고 다른 이전 값과 다른 값이 들어오면 카운트 변수인 cnt를 올리지 않고 반복문을 종료시켰다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main{
    static int n,k;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        visited = new boolean[100001];
        System.out.println(solve());
        System.out.println(cnt);
    }
    
    static int[] arr = new int[3];
    static int cnt = 0;
    static boolean[] visited;
    private static int solve() {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(n,0));
        visited[n] = true;
        int min = Integer.MAX_VALUE;
        while(!queue.isEmpty()) {
            Pair t = queue.poll();
            arr[0] = t.n-1;
            arr[1] = t.n+1;
            arr[2] = t.n*2;
            visited[t.n] = true;
            if(t.n==k) {
                min = Math.min(min, t.time);
                if(min!=t.time) break;
                cnt++;
            }
            for(int i=0;i<3;i++) {
                if(arr[i]>=0 && arr[i]<=100000 && !visited[arr[i]])
                    queue.add(new Pair(arr[i],t.time+1));
            }
        }
        return min;
    }
    
    static class Pair{
        private int n;
        private int time;
        public Pair(int n,int time) {
            this.n = n;
            this.time = time;
        }
    }
}