링크

숨바꼭질-1697

문제

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

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

입력

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

출력

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

Code

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 {
	public static int arr[]=new int[100001]; //시간초를 담는다.
	public static Queue<Integer> q=new LinkedList<Integer>();
	public static int n;
	public static int k;
	public static int result;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		n=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		q.add(n);
		
		if(n==k)
			System.out.println(0);
		else
		{
			BFS();
			System.out.println(result);
		}
	}
	
	public static void BFS()
	{
		int number=0;

		while(!q.isEmpty())
		{
			int now=q.poll();
			
			for(int i=0; i<3; i++)
			{
				if(i==0)
					number=now+1;
				else if(i==1)
					number=now-1;
				else if (i==2)
					number=now*2;
				
				if(number==k)
				{
					arr[number]=arr[now]+1;
					result=arr[number];
					return ;
				}
				
				else if(0<=number && number <100001 && arr[number]==0)
				{
					q.add(number);
					arr[number]=arr[now]+1;
				}
			}
			
		}
	}
}