백준 13549 숨바꼭질 3 (C++)

13549번: 숨바꼭질 3

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;
}