#백준_12851 숨바꼭질 2 - Java 자바

#유형 : BFS, 그래프탐색

#난이도 : 골드 V

#  1초 후에 X-1 또는 X+1로 이동 / 1초 후에 2*X의 위치로 이동을 주의해주면 된다.코드에 주석을 달아놓았다.

 

package bj;
 
import java.awt.Point;
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 p12851 {
    static int N,K,cnt,min=0;
    static int arr[] = new int[100001];
    static boolean visit[] = 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());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        bfs();
        System.out.println(min);
        System.out.println(cnt);
    }
    private static void bfs() {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<Point>();
//        수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다
        visit[N] = true;
        queue.add(new Point(N,0));
        
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            visit[po.x] = true;
            // 이미 목적지가 방문이 되어있는 경우
            if(min!=0 && min==po.y && po.x == K) {
                cnt++;
            }
            // 목적지 방문이 처음인 경우
            if(min ==0 && po.x == K) {
                min = po.y;
                cnt++;
            }
            //  1초 후에 X+1 
            if(po.x + 1 < 100001 && !visit[po.x+1])
                queue.add(new Point(po.x+1, po.y+1));
            //  1초 후에 X-1 
            if(po.x -1 >= 0 && !visit[po.x-1])
                queue.add(new Point(po.x-1, po.y+1));
            //  1초 후에 2*X
            if(po.x * 2 < 100001 && !visit[po.x*2])
                queue.add(new Point(po.x*2, po.y+1));
        }
    }
    
    
}