bfs를 이용한 문제이다. 기존 bfs와 비슷하게 흘러가지만 주의할 점이 있다. N = 1
일 때 1 + 1
과 1 * 2
가 구분이 안되게 된다. 구분을 하기 위해 푸시를 할 때 check[next] = true
를 해주는 것이 아닌 큐에서 꺼냈을 때 해주었다. 생각보다 시간이 걸린 문제였다.
#include <iostream>
#include <queue>
using namespace std;
int N, K, result1 = 0, result2 = 0;
int dx[2] = { 1,-1 };
bool check[100001];
void bfs() {
queue<pair<int, int>> q;
check[N] = true;
q.push({ N,0 });
while (!q.empty()) {
int now = q.front().first;
int count = q.front().second;
check[now] = true;
q.pop();
if (now == K) {
result1 = result1 == 0 ? count : result1;
if (result1 == count) result2++;
}
for (int i = -1; i < 2; i++) {
int next = i == -1 ? now * 2 : now + dx[i];
if (next < 0 || next > 100000) continue;
if (check[next]) continue;
q.push({ next, count + 1 });
}
}
}
void solution() {
bfs();
cout << result1 << "\n" << result2;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
solution();
return 0;
}