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

https://www.acmicpc.net/problem/13549

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

bool vst[300001];
int dx[] = {1, -1};

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

    int n, k;
    cin >> n >> k;

    queue<pair<int, int>> q;
    int cur, cnt;
    bool fin = false;

    q.emplace(n, 0);
    vst[n + 100000] = true;
    while (!fin) {
        cur = q.front().first;
        cnt = q.front().second;
        if (cur == k) {
            fin = true;
            break;
        }
        q.pop();
        int tmp = cur;
        while (tmp >= -100000 && tmp <= 200000) {
            for (int k = 0; k < 2; k++) {
                int nxt = tmp + dx[k];
                if (nxt >= -100000 && nxt <= 200000 &&  !vst[nxt + 100000]) {
                    q.emplace(nxt, cnt + 1);
                    vst[nxt + 100000] = true;
                }
            }
            tmp *= 2;
            if (tmp == k) {
                fin = true;
                break;
            }
            if (tmp == 0) break;
        }
    }

    cout << cnt << '\n';
}

나는 bfs로 풀었다. 대신 양수에서 2배, 음수에서 2배가 될 수 있기 때문에 칸은 -100000부터 100000까지로 생각한다. 따라서 vst 배열의 크기는 300001으로 설정하고 실제로 vst에 반영할 때 칸에 적힌 수 + 100000해서 반영하도록 했다. 

내가 처음에 틀렸던 이유는 2*x로 이동하는 건 시간이 들지 않아 무제한으로 쓸 수 있다는 점이고,  2*x로 이동 후 +1칸 또는 -1칸 이동할 필요 없이 바로 k에 도착하면 즉시 멈춰야 한다는 것이었다. (AC)