<aside> 💡 https://www.acmicpc.net/board/view/38887#comment-69010
원래 이 문제는 단순한 BFS를 요구하는 문제가 아닙니다.
왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문입니다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BFS를 쓸 수 없으나, 문제의 특성 때문에 방문 순서에 따라서 단순 BFS로도 우연히도 항상 정답을 찾을 수 있을 뿐입니다. 왜 하필 이 순서로 하면 항상 정답이 나오는가를 증명하는 건 매우 복잡한 일입니다.
이 문제를 보다 일반화된 경우 (가중치가 0인 간선이 있는 경우)에 대해 해결하려면, 즉, 이 문제의 의도대로 풀려면 다음과 같은 방법들을 사용할 수 있습니다.
0-1 BFS의 동작
왜 0-1 BFS가 O(V+E)에 동작할 수 있을까?
이는 BFS에서 노드를 관리하기 위해 큐를 사용하는 대신 덱(deque)을 사용하여 실현할 수 있다.
0-1 BFS는 다음 과정에 따라 최단 경로를 찾게 된다.
1. 덱의 front에서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
만약 현재 노드까지 비용 + 그 노드를 향하는 가중치 < 그 노드까지 가는데 소비된 비용이라면?
소비된 비용을 갱신해준다. 노드가 갱신된 상태에서,
만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
덱에서 더 이상 꺼낼 노드가 없을 때까지 이 과정을 반복한다.
<aside> 💡
위 알고리즘과 같이 약간 다익스트라?처럼 비용을 비교하는게 맞을 확률을 더 높이는 길이다.
</aside>
<aside>
💡 0-1bfs를 할 때 visited 에는 단순한 0, 1이 아니라 비용이 들어가는 게 맞는것 같다.
단순하게 0, 1을 넣어도 풀리는 문제가 있지만 아닌 문제도 있는 것 같다.
뭐 이동 순서를 바꾸면 되는 경우도 있지만, 그 순서를 알아내기가 더 어렵다. 즉, 이동순서가 바뀌면 동작이 안되는 경우가 있다…(push_front을 할 수 있는, 즉 비용이 0인 간선을 순서상 앞에 놓고, 나머지 뒤에 push_back할 애들을 놓으면 되는 경우가 있다. 항상 그런가..?)
</aside>
#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
#define endl '\\n';
using tp = tuple<int, int, int>;
using pp = pair<int, int>;
using ll = long long;
#define MAX 100001
int N, K, visited[MAX], ans;
void solve()
{
memset(visited, -1, sizeof(visited));
deque<int> q;
visited[N] = 0;
q.push_back(N);
while (!q.empty())
{
int cur = q.front();
int t = visited[cur];
q.pop_front();
// base case
if (cur == K)
{
ans = t;
return;
}
// x*2
int next = (cur << 1);
if (next < MAX && visited[next] == -1)
{
visited[next] = t;
q.push_front(next);
}
// x-1
next = cur - 1;
if (0 <= next && visited[next] == -1)
{
visited[next] = t + 1;
q.push_back(next);
}
// x+1
next = cur + 1;
if (next < MAX && visited[next] == -1)
{
visited[next] = t + 1;
q.push_back(next);
}
}
}
int main()
{
fastio;
cin >> N >> K;
solve();
cout << ans << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
#define fastio cin.tie(0)->sync_with_stdio(0)
#define endl '\\n';
using tp = tuple<int, int, int>;
using pp = pair<int, int>;
using ll = long long;
#define MAX 200001
int N, K, visited[MAX], ans;
void solve()
{
fill(visited, visited + MAX, MAX);
deque<int> q;
visited[N] = 0;
q.push_back(N);
while (!q.empty())
{
int cur = q.front();
int t = visited[cur];
q.pop_front();
// base case
if (cur == K)
{
ans = t;
return;
}
// x-1
int next = cur - 1;
if (0 <= next && visited[next] > t + 1)
{
visited[next] = t + 1;
q.push_back(next);
}
// x+1
next = cur + 1;
if (next < MAX && visited[next] > t + 1)
{
visited[next] = t + 1;
q.push_back(next);
}
// x*2
next = cur << 1;
if (next < MAX && visited[next] > t)
{
visited[next] = t;
// 0-1 bfs -> cost 0: push_front
q.push_front(next);
}
}
}
int main()
{
fastio;
cin >> N >> K;
solve();
cout << ans << endl;
return 0;
}