[java] 백준 숨바꼭질3

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

 

13549번: 숨바꼭질 3

 

 

*2와 +1이 먼저 도달하기 때문에 앞순서에 와야한다!

도달했을 때 time이 작은 것을 가져온다.

 

import java.io.*;
import java.util.*;

class point{
	int n,s;
	point(int n,int s){
		this.n=n;
		this.s=s;
	}
}
public class Main {
	static int k;
	static int s;
	static int max = 100000;
	static int min = Integer.MAX_VALUE;
	
	static void BFS(int n) {
		Queue<point> q = new LinkedList<>();
		boolean[] visited = new boolean[100001];
		
		q.add(new point(n,0));
		
		
		while(!q.isEmpty()) {
			point now = q.poll();
			visited[now.n] = true;
			
			if(now.n == k) {
				min = Math.min(min, now.s);
			}
			
			if(now.n*2 <= max  && !visited[now.n*2]) {
				q.add(new point(now.n*2,now.s));
				}
				
			if(now.n+1 <= max  && !visited[now.n+1]) {
					q.add(new point(now.n+1,now.s+1));
				
				}	
						
			if(now.n-1 >= 0 && !visited[now.n-1]) {
				q.add(new point(now.n-1,now.s+1));
				
			}
		
			}
	}
		

	
	public static void main(String[] args) throws IOException  {
	
		Scanner sc = new Scanner(System.in);
		
		s = sc.nextInt();
		k = sc.nextInt();
		
		BFS(s);
		System.out.println(min);
	}}