[백준] 12851 숨바꼭질 2(자바) : BFS

이 문제가 잘 이해가 안된다면 백준 1697번 문제를 풀고 오세요 !! 

문제 설명

문제

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

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

입력

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

출력

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

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

예제 입력 1 

5 17

예제 출력 1 

4
2

 

 

풀이 코드

1697번 숨바꼭질 코드에서, 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 구하는 코드만 추가하면된다.

최단 시간 깊이에서 수빈이가 동생의 위치에 도달한 횟수를 세면 된다.

 

숨바꼭질 1 코드와 다른 점은,

숨바꼭질 1에서는 queue에 1초 후에 방문할 노드들을 저장할때 visited를 true로 바꿔주었다면, 

숨바꼭질 2에서는 queue에서 노드들을 꺼낼 때 visited 를 true로 바꿔준다.

이렇게 되면 같은 깊이(시간) 에서 중복된 노드들이 queue에 쌓일 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

    static int subin, sister;
    static boolean[] visited = new boolean[100001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st  = new StringTokenizer(br.readLine());

        subin = Integer.parseInt(st.nextToken());
        sister = Integer.parseInt(st.nextToken());
        search(subin, sister);
    }
    static void search(int subin, int sister){
        Queue<Integer> q = new LinkedList<>();
        q.add(subin);
        visited[subin] = true;
        int time =0, cnt = 0;
        while(true){
            int size = q.size();
            for(int i = 0; i<size; i++){
                int current = q.poll();
                visited[current] = true;

                if(current == sister){
                    cnt ++;
                    continue;
                }
                if(current*2 <= 100000 && !visited[current*2]) {
                    q.add(2* current);
                }
                if(current+1 <= 100000 && !visited[current+1]){
                    q.add(current +1 );
                }
                if(current-1 >= 0 && !visited[current-1]){
                    q.add(current -1);
                }
            }
            if(cnt >0) {System.out.println(time); System.out.println(cnt); return;}
            time++;
        }
    }
}