[백준/12851] 숨바꼭질 2 - Java 자바

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

 

개념: 그래프 탐색, bfs

 

 

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

 

---

 

풀이

이전 문제 숨바꼭질3 과 유사하다. 최소 시간과 더불어 최소 시간으로 방문하는 경로의 수를 함께 구해야 한다는 점이 차이점이다. 

 

 

전체 코드

import java.util.*;

public class Main {
    static int N, K, count;
    static int max = 100000;
    static int[] time;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();
        time = new int[max + 1];
        Arrays.fill(time, Integer.MAX_VALUE);

        bfs();
        System.out.println(time[K]);
        System.out.println(count);
    }

    public static void bfs() {
        Deque<Integer> q = new ArrayDeque<>();
        q.offer(N);
        time[N] = 0; // 시작점의 시간은 0

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

            if (current == K) {
                count++;
                continue; // 다른 경로도 확인
            }

            int[] nextPositions = {current * 2, current + 1, current - 1};
            for (int next : nextPositions) {
                // next가 범위 밖이거나, 이미 방문한 위치인데 기존보다 더 오래 걸리는 경로라면 큐에 추가X
                if (next < 0 || next > max || (time[next] < time[current] + 1)) continue;
                time[next] = time[current] + 1;
                q.add(next);
            }
        }
    }
}