[백준] 13549 숨바꼭질 3

[백준] 13549 숨바꼭질 3

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

• [백준] 1697 숨바꼭질 문제에서 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다는 조건만 변경하면 된다

#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), 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;
}

📌참고자료

• [백준] 1697 숨바꼭질
  https://velog.io/@sunjoo9912/%EB%B0%B1%EC%A4%80-1697-%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88