백준 13549 숨바꼭질 3

백준 13549

이 문제는 숨바꼭질1 문제와 달리 원래 거리에서 2배를 해서 0초 안에 갈 수 있다. 이 숨바꼭질 문제들은 이동하는 순서에 따라 답이 틀려지게 된다.

숨바꼭질1에서는 2배를 해서 갈 때, 1초가 걸린다. 그래서 n과 k에 0과 2가 입력 됐을 때, cur2 , cur+1 ,cur-1 순서라면 0 -> 0 -> 1 -> 2로 답이 3이 나오고 cur+1 ,cur2 ,cur-1 순서라면 0 -> 1-> 2로 답이 2가 나온다. 이렇게 순서에 따라 답이 다르게 도출된다.

숨바꼭질3에서는 cur*2 , cur-1 ,cur+1 순서가 되어야 한다.

ex)
for문에서 cur2 , cur+1 ,cur-1 순서 일 때
4 6 => 4 -> 5 -> 6
답 : 2
for문에서 cur2 , cur-1 ,cur+1 순서 일 때
4 6 => 4 -> 3 -> 6
답 : 1

#include<bits/stdc++.h>
#define INF 987654321
using namespace std;
int n, k;
int vis[100001];
queue<int> q;
int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	cin >> n >> k;

	fill(vis, vis + 100001, -1);

	q.push(n);
	vis[n] = 0;

	while (!q.empty()) {
		int cur = q.front();
		q.pop();

		if (cur == k) break;

		for (int i = 0; i < 3; i++) {

			if (i == 0) {
				int nxt = cur * 2;
				if (nxt < 0 || nxt>100000) continue;
				if (vis[nxt]<0) {
					vis[nxt] = vis[cur];
					q.push(nxt);
				}
			}
			else {
				int nxt;
				if (i == 1) {
					nxt = cur - 1;
				}
				else {
					nxt = cur + 1;
				}
				if (nxt < 0 || nxt>100000) continue;
				if (vis[nxt]<0) {
					vis[nxt] = vis[cur]+1;
					q.push(nxt);
				}
			}

		}
	}
	cout << vis[k] << '\n';
}