문제

Code

#include <iostream>
#include <queue>
#include <utility>

using namespace std;

int dist[200002];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    queue<int> Q;
    int N, K;

    cin >> N >> K;
    if(N == K)
    {
        cout << 0 ;
        return 0;
    }
    fill(dist, dist+200000,-1);
    dist[N] = 0;
    Q.push(N);

    while(!Q.empty())
    {
        auto cur = Q.front(); Q.pop();
        int dx[3]={-1, +1, cur};
        for(int dir=0;dir<3;dir++)
        {
            int nx = cur +dx[dir];
            if(nx < 0 || nx > 200000) continue;
            if(dist[nx] != -1) continue;
            dist[nx] = dist[cur] + 1;
            Q.push(nx);
            if(nx == K)
            {
                cout << dist[nx];
                return 0;
            }
        }
    }
}

• 아이디어의 핵심은 BFS를 1차원에서도 사용할 수 있다는 생각
• 1차원이든 / 2차원이든 정점사이의 거리를 구할 때 BFS를 사용할 수 있다는 생각!
• 값이 변할 수 있는 범위(-1 / +1 / 2*cur)은 dx[3]으로 해결

---

[ 주의 ]

이 문제는 운 좋게 수빈이가 100,000 이하에서 움직이는게 가장 효율적이지만, 이렇게 값에 변화를 추구하는 상황에서 반드시 입력이 100,000 이하에서 처리될 것이라고 생각하지 않는것이 매우 중요!!!!!
(2배가 곱해져서 가장 효율적이 될 수 있기 때문에 200,000으로 잡았다)