문제

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

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

입력

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

출력

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

풀이

해당 문제는 bfs로 풀면서 이전의 값의 +1를 해주는 형태로 풀어주면 된다.
배열의 크기를 최대 100000까지 생성하고 걷기(x-1, x+1), 순간이동(x * 2)를 했을때 배열의 범위를 벗어나는지 확인한 뒤 bfs를 수행하면 된다.

visited 배열에는 이동한 시간이 저장되는데 처음 위치에서의 값은 0으로 하여 출력할 때 visited[k] 형태로 할 수있다.

소스

import java.util.*;

public class Main {
	public static int n, k;

	// 해당 인덱스까지 걸린 시간
	public static int[] visited = new int[100001];

	public static void bfs(int x) {
		Queue<Integer> q = new LinkedList<>();

		q.offer(x);
		visited[x] = 0;

		while (!q.isEmpty()) {
			int now = q.poll();

			// 위치가 같을 경우
			if (now == k) {
				break;
			}

			// 걷기(x-1, x+1), 순간이동 (2*x)
			if (now + 1 <= 100000 && visited[now + 1] == 0) {
				q.offer(now + 1);
				visited[now + 1] = visited[now] + 1;
			}

			if (now - 1 >= 0 && visited[now - 1] == 0) {
				q.offer(now - 1);
				visited[now - 1] = visited[now] + 1;
			}

			if (now * 2 <= 100000 && visited[now * 2] == 0) {
				q.offer(now * 2);
				visited[now * 2] = visited[now] + 1;
			}

		}

		System.out.println(visited[k]);

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		k = sc.nextInt();

		bfs(n);

	}

}