BOJ 12851 숨바꼭질2

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

12851번: 숨바꼭질 2

 

import java.io.*;
import java.util.*;
public class Main
{   
    static int n;
	static int m;
	
	
	public static class Node{
	    int x;
	    int step;
	    
	    public Node(int x, int step){
	        this.x=x;
	        this.step =step;
	    }
	} 
	
	public static int[] bfs(Node start){
	    Queue<Node> q = new LinkedList();
	    boolean[] visited = new boolean[100_001];
	    int min_time=100_001;
	    int count=0;
        q.offer(start);
        while(q.size()>0){
            Node node = q.poll();
            if(node.step>min_time) break;
            if(node.x==m){
                min_time = node.step;
                count++;
                continue;
            }
            visited[node.x]=true;
            int[] next= {node.x+1,node.x-1,node.x*2};
            for(int i=0;i<3;i++){
                if(next[i]<= 100_000 && next[i]>=0 && !visited[next[i]]){
                    
                    q.offer(new Node(next[i],node.step+1));
                    
                }
                
            }
        }
	    return new int[]{min_time,count};
	}
		
    
    
    
    
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input1 = br.readLine().split(" ");
		n = Integer.parseInt(input1[0]);
		m = Integer.parseInt(input1[1]);
		
		int[] ans = bfs(new Node(n,0));
		System.out.println(ans[0]);
		System.out.println(ans[1]);
		
		
		
	}
}

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

class Main {
    static int n, k;
    static int[] visited = new int[100001];
    static int[] count = new int[100001];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();
        q.add(n);
        visited[n] = 1;
        count[n] = 1;
        while (!q.isEmpty()) {
            int now = q.poll();

            if (now == k) break;
            int[] next = {now - 1, now + 1, now * 2};
            for (int i = 0; i < 3; i++) {
                if(!isRange(next[i])) continue;
                if (visited[next[i]] == 0) {
                    visited[next[i]] = visited[now] + 1;
                    count[next[i]] = count[now];
                    q.add(next[i]);
                } else if (visited[next[i]] == visited[now] + 1) {
                    count[next[i]] += count[now];
                }
            }
        }
        System.out.println(visited[k] - 1);
        System.out.println(count[k]);
    }
    static boolean isRange(int x) {
        return x >= 0 && x <= 100000;
    }
}