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

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

 

#include <bits/stdc++.h>
using namespace std;

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

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

    int maxs = 100001;
    vector<bool> vst = vector<bool>(maxs, false);

    int cnt = 0;
    bool fin = false;
    queue<int> q;
    q.push(n);
    vst[n] = true;
    
    while(!q.empty()) {
        int tmp = q.size();
        for (int i = 0; i < tmp; i++) {
            int cur = q.front();
            q.pop();
            if (cur == k) {
                fin = true;
            }
            if ((cur - 1) >= 0 && (cur - 1) < maxs) {
                if (!vst[cur - 1]) {
                    q.push(cur - 1);
                    vst[cur - 1] = true;
                }
            }
            if ((cur + 1) >= 0 && (cur + 1) < maxs) {
                if (!vst[cur + 1]) {
                    q.push(cur + 1);
                    vst[cur + 1] = true;
                }
            }
            if ((cur * 2) >= 0 && (cur * 2) < maxs) {
                if (!vst[cur * 2]) {
                    q.push(cur * 2);
                    vst[cur * 2] = true;
                }
            }
        }
        if (fin) {
            break;
        }
        cnt++;
    }

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

처음에는 dp가 생각나서 dp로 풀다가 뭔가 어렵고 복잡하고 이상해서..?? 태그를 봐버렸다... 근데 태그에 너비 우선 탐색이 있길래 아 난 왜 이런 쉬운 방법을 두고... 하면서 멍청한 나를 탓했다.

암튼 그래서 bfs로 풀어서 제출했는데 메모리 초과가 났다. (오답) 왜인가 했더니 이미 방문한 칸도 전부 q에 넣어서 q가 터진 것 같았다. 그래서 visited 벡터를 만들어 확인해서 넣도록 했다.

그렇게 했는데도 메모리 초과... (오답) 메모리가 좀 빡빡한 문제인걸까 암튼 visited 배열의 크기를 2 * max(n, k)에서 100001로 바꿔주니까 해결되었다. (정답)