[백준] 1697 숨바꼭질

[백준] 1697 숨바꼭질

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

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int getMinMove(int start, int end) {
	
	//<-curMove, curX>
	priority_queue<pair<int, int>> q;
	q.push({ 0, start });
	
	int visited[100001] = { 0 };

	while (!q.empty()) {
		int curMove = -q.top().first;
		int curX = q.top().second;
		q.pop();

		if (curX == end) return curMove;

		if (visited[curX]) continue;
		visited[curX] = 1;

		if ((curX - 1 >= 0) && (!visited[curX - 1]))
			q.push({ -(curMove + 1), curX - 1 });

		if ((curX + 1 <= 100000) && (!visited[curX + 1]))
			q.push({ -(curMove + 1), curX + 1 });

		if ((curX *2 <= 100000) && (!visited[curX*2]))
			q.push({ -(curMove + 1), curX*2 });
	}

	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, K;
	cin >> N >> K;
	cout << getMinMove(N, K);
	return 0;
}