(c++) 백준 "1697) 숨바꼭질"

1. 숨바꼭질 https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

#include <iostream>
#include <queue>
using namespace std;

int N, K;
int board[500000];
queue<int> q;
bool check(int now, int next) {// next < K*3 &&
	if (0 <= next && next < K * 2 && board[next] == 0) {
		return true;
	}
	return false;
}

void qInput(int now, int next) {
	board[next] = board[now] + 1;
	q.push(next);
}

int main() {
	cin >> N >> K;
	if (K <= N) {
		cout << N - K << endl;
		return 0;
	}
	q.push(N);
	while (!q.empty()) { //순서바꾸니 맞음 왜?
		int now = q.front();
		q.pop();
		if (now == K) {
			break;
		}
		int next;
		next = now + 1;
		if (check(now, next)) {
			qInput(now, next);
		}
		next = now - 1;
		if (check(now, next)) {
			qInput(now, next);
		}
		next = now * 2;
		if (check(now, next)) {
			qInput(now, next);
		}
	}
	board[N] = 0;
	cout << board[K] << endl;
	return 0;
}

처음에는 순서를 *2, -1, +1로 순서를 지정하지 않았다 그러니 50%대에서 실패가 나왔다.

질문하기를 뒤지다가 나와 같은 케이스인 사람을 발견했다.

그 사람은 +1 -1 *2 순서로 bfs를 돌려서 통과를 했다고 한다.

해당 내용을 참고로 내 순서도 바꾸니 성공이 되었다. 왜 그런지는 차근차근 살펴봐야겠다.