1697 숨바꼭질

#include <stdio.h>
#include <queue>
#include <utility>
 
using namespace std;
 
int dx[3] = { -1,1 };
 
int bfs(int n, int k) {
    queue<pair<int, int>> q;
    q.push(make_pair(0, n));
 
    int chk[200001] = { 0 };
    while (!q.empty()) {
        int len = q.front().first;
        int x = q.front().second;
 
        q.pop();
        if (x == k) {
            return len;
        }
                
        for (int i = 0; i < 3; i++) {
            int xx;
            if (i == 2) {
                xx = x * 2;
            }
            else {
                xx = x + dx[i];
            }
 
            if (xx < 0 || xx>200000)
                continue;
            if (chk[xx] == 1)
                continue;
 
            chk[xx] = 1;
            q.push(make_pair(len+1, xx));
        }
    }
}
 
int main() {
    int n, k;
    scanf("%d %d", &n, &k);
 
    printf("%d",bfs(n, k));
}

배열 메모리 초과를 해결하는 것이 관건이었다.

200000을 초과하는 경우, 아예 고려하지 않는 방식을 취했다. 

100000 이상을 threshold로 설정했을 경우, 틀릴수도 있으니 주의하기