[12851] 숨바꼭질 2

풀이

1. 1에서 2로 갈 때 x2를 하는 것과 +1을 하는 것을 서로 다른 방법으로 count 해주어야 한다.
2. queue에서 뺄 때 visit을 해주어서 같은 sec일 때는 하나의 값이 queue에 여러번 들어갈 수 있도록 해야한다.
3. 1 / 2 2 0 / 4 3 4 3 / … : 아래 코드에서 q.size()를 기록하고 for문을 돌리는 것으로 sec마다 몇 번의 ‘앞에서 빼서 뒤에 넣는 과정’을 해야하는지 구현할 수 있다.

예시 1

1 7 4 4

1 -> 2(x2) -> 4 -> 8 -> 7
1 -> 2(+1) -> 4 -> 8 -> 7
1 -> 2(x2) -> 4 -> 8 -> 7
1 -> 2(+1) -> 3 -> 6 -> 7

코드

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int n = 0, k = 0, sec = 0;
bool check[100001];
pair<int,int> bfs(int x) {
	queue<int> q;
	q.push(x);
	int curr = 0, next = 0, ans=0, loop = 0;
	while (!q.empty()) {
		loop = q.size();
		for (int i = 0; i < loop; i++) {
			curr = q.front(); q.pop();
			check[curr] = true;
			if (curr == k) 	ans += 1;
			next = curr * 2;
			if (next <= 100000 && check[next] == false)	q.push(next);
			next = curr + 1;
			if (next <= 100000 && check[next] == false) q.push(next);
			next = curr - 1;
			if (0 <= next && check[next] == false) q.push(next);
		}
		if (ans != 0) {
			return make_pair(sec, ans);
		}
		sec += 1;
	}
}

int main(void) {
	scanf("%d%d", &n, &k);
	pair<int, int> res = bfs(n);
	printf("%d\n", res.first);
	printf("%d\n", res.second);
	return 0;
}