백준 1697 숨바꼭질 (C++)

1695번: 숨바꼭질

dp같아 보이는 bfs문제이다. N이 K에 도착했을 때 최소 시간을 구하는 문제로 처음에 dp로 접근해서 생각을 하느라 시간이 좀 걸렸다. 생각해보니 굳이 dp를 쓸게 아니라 bfs로 제일 먼저 K에 도착한 것이 최소 시간이 된다는 것을 깨닫고 bfs로 풀었다. -1, +1, *2 세가지 경우로 bfs를 돌며 이미 지나온 값은 먼저 지나갔기에 더 짧은 시간이므로 다시 큐에 넣지 않도록 check함수로 구분했다.

#include <iostream>
#include <queue>

using namespace std;

int N, K, res = 0;
int dir[2] = { -1,1 };
bool check[100000];

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

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

    while (!q.empty()) {
        int cur = q.front().first;
        int time = q.front().second;

        q.pop();

        if (cur == K) {
            res = time;
            break;
        }

        for (int i = 0; i < 3; i++) {
            int next;

            if (i == 2) {
                next = cur * 2;
            }
            else {
                next = cur + dir[i];
            }
            
            if (next < 0 || next > 100000) continue;
            if (check[next]) continue;

            q.push({ next,time + 1 });
            check[next] = true;
        }
    }
}

void solution() {
    bfs();

    cout << res;
}

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

    cin >> N >> K;

    solution();

    return 0;
}