[Algorithm /백준] 12851 숨바꼭질 2

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

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

[입력]
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

[출력]
첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.


[문제 해결 - bfs]

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[] arr;
    static int[] count;
    static boolean[] visited;

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

        int N = sc.nextInt();
        int K = sc.nextInt();

        arr = new int[100001];
        count = new int[100001];
        visited = new boolean[100001];

        bfs(N, K);
        
        System.out.println(arr[K]);
        System.out.println(count[K]);
    }

    public static void bfs(int start, int target) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        visited[start] = true;
        arr[start] = 0;
        count[start] = 1;

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

            for (int next : new int[]{current - 1, current + 1, current * 2}) {
                if (next >= 0 && next <= 100000) {
                    if (!visited[next]) {
                        q.offer(next);
                        visited[next] = true;
                        arr[next] = arr[current] + 1;
                        count[next] = count[current];
                    } else if (arr[next] == arr[current] + 1) {
                        count[next] += count[current];
                    }
                }
            }
        }
    }
}

 

 

+) 기존의 숨바꼭질 문제에서 해당 최단 경로에 접근하는 방법의 갯수를 구한 문제.

 

만약 bfs를 두번 사용하게 되면 메모리 초과가 발생하게 된다.

따라서 방문하지 않을 경우와 방문했을 경우를 체크해서 문제풀이를 하면 된다.