0-1 bfs를 응용한 문제였다. 0-1 bfs 유형은 처음이라 푸는데 시간이 오래 걸렸다. 수빈이의 위치에서 동생을 찾는 최단 시간을 구하면 되는데 이는 0-1 bfs 뿐 아니라 다익스트라로도 풀 수 있다. 0-1 bfs를 구현하기 위해 deque
을 사용했다. 이유는 가중치가 0인 순간 이동의 경우 가중치가 1인 걷기가 먼저 도착하여 check
가 true가 되면 시간이 더 짧은 순간 이동이 도착해도 무시되기 때문에 이를 방지하기 위해 순간 이동의 경우 deque
을 사용하여 push_front
로 우선으로 접근하도록 저장하였다.
처음에는 단순히 bfs로 풀었는데 안되서 시간이 오래 걸렸다. 문제 흐름을 잘 이해하고 알고리즘을 작성해야겠다.
#include <iostream>
#include <deque>
using namespace std;
int N, K, res = 0;
bool check[100001];
void bfs() {
deque<pair<int, int>> q;
check[N] = true;
q.push_back({ N,0 });
while (!q.empty()) {
int n = q.front().first;
int time = q.front().second;
q.pop_front();
if (n == K) {
res = time;
break;
}
if (n * 2 < 100001 && !check[n * 2]) {
check[n * 2] = true;
q.push_front({ n * 2,time });
}
if (n + 1 < 100001 && !check[n + 1]) {
check[n + 1] = true;
q.push_back({ n + 1,time + 1 });
}
if (n - 1 >= 0 && !check[n - 1]) {
check[n - 1] = true;
q.push_back({ n - 1,time + 1 });
}
}
}
void solution() {
bfs();
cout << res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
solution();
return 0;
}