코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
int check[100001];
int dist[100001];
void bfs(int n, int k)
{
    deque<int> q;
    q.push_back(n);
    while (!q.empty())
    {
        int temp = q.front();
        q.pop_front();
        if (temp == k)
            break;
        if (0 <= temp * 2 && temp * 2 <= 100000 && check[temp * 2] == 0)
        {
            check[temp * 2] = 1;
            dist[temp * 2] = dist[temp];
            q.push_front(temp * 2);
        }
        if (0 <= temp - 1 && temp - 1 <= 100000 && check[temp - 1] == 0)
        {
            check[temp - 1] = 1;
            dist[temp - 1] = 1 + dist[temp];
            q.push_back(temp - 1);
        }
        if (0 <= temp + 1 && temp + 1 <= 100000 && check[temp + 1] == 0)
        {
            check[temp + 1] = 1;
            dist[temp + 1] = 1 + dist[temp];
            q.push_back(temp + 1);
        }
    }
}
int main(void)
{
    int n, k;
    cin >> n >> k;
    bfs(n, k);
    cout << dist[k];
    return 0;
}

문제 접근

너비 우선 탐색을 이용

해결 방법

중요한 것은 순간이동을 하면 0초가 걸리고, 순간이동을 하지 않는 이동은 1초가 더 늘어난다는 사실. 그래서 순간이동의 우선순위를 먼저 따져줘야함. 따라서 덱을 이용해서 순간이동을 front 에 집어넣고, 보통 이동은 back 에 집어넣어주므로써 해결 가능하다.