문제

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

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

입력

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

출력

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

예제

---

풀이

수빈이가 동생이 있는 좌표까지 이동하는 데 걸리는 최소 시간 (경로)을 구하는 문제이므로 BFS를 사용해야 한다. 그런데, 좌표 상에서 이동할 때 순간이동은 0초, 걷는 것은 1초가 걸리므로 순간이동의 우선순위가 더 높다. (그래프 용어로 표현하자면, n에서 k까지의 최단 경로를 구하려고 하는데 순간이동이냐 걷느냐에 따라 간선의 가중치가 0과 1로 달라지는 것이다.)
따라서, 해당 좌표까지 이전에 도달한 게 최소 시간인지, 지금 도달하는 게 최소 시간인지 비교하고 최솟값을 갱신해주는 작업이 필요하다. 이 부분에서 다익스트라 알고리즘의 개념이 사용된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#define MAX 100001  
using namespace std; 

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k; // 수빈이와 동생의 위치 
	cin >> n >> k;

	int minTime[MAX]; // 각 좌표에 도달하는 최소 시간 저장 
	for(int i = 0; i < MAX; i++){ 
		minTime[i] = 1e9; 
	}

	queue<pair<int, int>> q; // {수빈의 위치, 해당 지점까지 걸린 시간}
	q.push({ n, 0 }); 
	minTime[n] = 0; 

	while(!q.empty()){
		int x = q.front().first; 
		int time = q.front().second; 
		q.pop(); 

		vector<int> nextX = { x + 1, x - 1, x * 2 };
		for(int i = 0; i < 3; i++){
			if(0 <= nextX[i] && nextX[i] < MAX) {
				int tempTime = time; 
				if(i != 2) tempTime++; 
				
				if(minTime[nextX[i]] > tempTime){
					minTime[nextX[i]] = tempTime;
					q.push({ nextX[i], tempTime });  
				}
			}
		}
	}

	// n에서 k까지 도달하는 데 걸린 최소 시간 출력 
	cout << minTime[k]; 
	
	return 0; 
}