[1697] 숨바꼭질

문제

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

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

입력

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

출력

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

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

1697번: 숨바꼭질

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

public class Main {
	static int[] MAP;
	static boolean[] VISIT;
	static int N, K;
	static int dx[] = {-1,1,2};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		K = sc.nextInt();
		MAP = new int[100001];
		VISIT = new boolean[100001];
		bfs();
	}

	private static void bfs() {
		Queue<COUNT> q = new LinkedList<COUNT>();
		q.offer(new COUNT(N, 0));
		VISIT[N] = true;
		
		while(!q.isEmpty()) {
			COUNT c = q.poll();
			
			if(c.now==K) {
				System.out.println(c.cnt);
				return;
			}
			for(int i=0; i<3; i++) {
				int nextX = c.now;
				int nextCnt = c.cnt+1;
				if(i<2) {
					nextX+=dx[i];
				}else {
					nextX = c.now*dx[i];
				}
				
				
				
				if(nextX<0||nextX>=100001)
					continue;
				
				if(VISIT[nextX])
					continue;
                
				q.offer(new COUNT(nextX,nextCnt));
                VISIT[nextX] = true;
			}
		}
		
		
	}

}

class COUNT{
	int now;
	int cnt;
	COUNT(int now, int cnt){
		this.now = now;
		this.cnt = cnt;
	}
}