백준 12851 숨바꼭질 2 (C++)

12851번: 숨바꼭질 2

bfs를 이용한 문제이다. 기존 bfs와 비슷하게 흘러가지만 주의할 점이 있다. N = 1일 때 1 + 1과 1 * 2가 구분이 안되게 된다. 구분을 하기 위해 푸시를 할 때 check[next] = true를 해주는 것이 아닌 큐에서 꺼냈을 때 해주었다. 생각보다 시간이 걸린 문제였다.

#include <iostream>
#include <queue>

using namespace std;

int N, K, result1 = 0, result2 = 0;
int dx[2] = { 1,-1 };
bool check[100001];

void bfs() {
    queue<pair<int, int>> q;

    check[N] = true;
    q.push({ N,0 });

    while (!q.empty()) {
        int now = q.front().first;
        int count = q.front().second;
        
        check[now] = true;
        q.pop();

        if (now == K) {
            result1 = result1 == 0 ? count : result1;
            if (result1 == count) result2++;
        }

        for (int i = -1; i < 2; i++) {
            int next = i == -1 ? now * 2 : now + dx[i];

            if (next < 0 || next > 100000) continue;
            if (check[next]) continue;

            q.push({ next, count + 1 });
        }
    }
}

void solution() {
    bfs();
    cout << result1 << "\n" << result2;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> K;

    solution();

    return 0;
}