숨바꼭질 3 (Gold V)

문제 링크

문제 설명

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

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

입력

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

출력

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

문제 풀이

• 이 문제는 숨바꼭질 문제랑 비슷해서 아 그냥 시간만 바꿔주면 되는구나? 생각했는데 경기도 오산이었다.
• 근데 방문한적이 있더라도 time 증가 없이 이동할 경우 더 빠르게 방문할 수 있으므로 int[] 배열이 0이 아닐때 큐에 넣는 방식은 틀리게 된다!!
• 그래서 해결 방법은 그냥 que.add 순서 바꿔주기 !
• 1에서 2로가는데는 +1 보다 *2 가 더 빠르므로 *2를 먼저 체크해주고 queue에 넣어주는 걸로 해결 !

Solution

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

// 숨바꼭질 3
public class Main {
	static int[] check = new int[100001];
	static int N, K;

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

		if (N == K)
			System.out.println(0); // 입력이 같을 때
		else {
			bfs();
			System.out.println(check[K]-1);
		}
	}

	public static void bfs() {
		Queue<Integer> que = new LinkedList<>();
		que.add(N);
        check[N] = 1;
		while (!que.isEmpty()) {
			int X = que.poll();
			if (X == K)
				break;
            
            if (X * 2 < check.length && check[X * 2] == 0) { // X*2
				que.add(X * 2);
				check[X * 2] = check[X]; // 0초후
			}
			if (X > 0 && check[X - 1] == 0) { // X-1
				que.add(X - 1);
				check[X - 1] = check[X] + 1; // 1초후
			}
			if (X + 1 < check.length && check[X + 1] == 0) { // X+1
				que.add(X + 1);
				check[X + 1] = check[X] + 1; // 1초후
			}
			

		}
	}
}