수빈이가 n, 동생이 k의 위치에 있을 때 수빈이가 동생을 찾기 위해서 몇 번 이동해야 하는지 구해야 한다.
조심해야 할 부분
- 수빈이와 동생이 같은 위치에 있을 경우
go[3]배열을 선언해 한 칸 앞으로 갈 경우, 한 칸 뒤로 갈 경우, 현재 위치의 두 배가 되는 위치로 점프할 경우를 한 번에 처리해줬다.
#include <iostream>
using namespace std;
#include <queue>
queue<int> q;
int dist[100001] = { 0 };
bool visited[100001] = { false };
int n, k;
int ans;
void bfs() {
q.push(n);
visited[n] = true;
while (!q.empty()) {
int n = q.front();
q.pop();
int go[3] = { n - 1, n + 1, 2 * n }; // 한 칸 앞, 한 칸 뒤, 두배 점프
for (int i = 0; i < 3; i++) {
int nx = go[i];
if (0 <= nx && nx <= 100000 && !visited[nx]) {
q.push(nx);
visited[nx] = true;
dist[nx] = dist[n] + 1;
}
if (nx == k) {
ans = dist[nx];
return;
}
}
}
}
int main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
if (n == k) {
cout << '0';
}
else {
bfs();
cout << ans;
}
}