[1697] 숨바꼭질 1

풀이

1. 시작 위치에서 다음 위치로 갈 수 있는 값을 큐에 넣습니다.
2. 큐에 넣으면서 다음 위치까지 걸리는 시간 = 현재까지 걸린 시간 +1로 저장합니다.
3. 큐에서 하나씩 빼면서 목적지와 같은지 확인합니다.

주의

1. index 접근을 할 때에 범위 판단을 먼저 해야 out of index error가 나지 않습니다.
2. N 0 을 입력했을 때 답은 N입니다.

코드

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

int n = 0, m = 0;
int check[100001];
int bfs(int x) {
	queue<int> q;
	check[x] = 0;
	q.push(x);
	int curr = 0, next = 0;
	while (!q.empty()) {
		curr = q.front(); q.pop();
		if (curr == m) return check[m];
		next = curr + 1;
		if (0 <= next && next <= 100000 && check[next] == -1) {
			check[next] = check[curr] + 1;
			q.push(next);
		}
		next = curr - 1;
		if (0 <= next && next <= 100000 && check[next] == -1) {
			check[next] = check[curr] + 1;
			q.push(next);
		}
		next = curr * 2;
		if (0 <= next && next <= 100000 && check[next] == -1) {
			check[next] = check[curr] + 1;
			q.push(next);
		}
	}
}

int main(void) {
	memset(check, -1, sizeof(check));
	scanf("%d%d", &n, &m);
	printf("%d\n", bfs(n));
	return 0;
}