[백준] 1697번: 숨바꼭질

#include <cstdio>
#include <queue>
#include <cmath>

using namespace std;

int main(int argc, const char * argv[]) {
    int N, K, level, frontnum;
    queue<int> q;
    int arr[100001] = {0, };
    scanf("%d %d", &N, &K);
    if(N>=K){
        level = N-K;
    }
    else{
        q.push(N);
        arr[q.front()] = 0;
        while(q.front() != K){
            frontnum = q.front();
            q.pop();
            //printf("%d\n",frontnum);
            if(arr[frontnum-1] == 0 && frontnum-1 >= 0 && frontnum-1 <= 100000){
                q.push(frontnum-1);
                arr[frontnum-1] = arr[frontnum] + 1;
            }
            if(arr[frontnum+1] == 0 && frontnum+1 >= 0 && frontnum + 1 <= 100000){
                q.push(frontnum+1);
                arr[frontnum+1] = arr[frontnum] + 1;
            }
            if(arr[frontnum*2] == 0 && frontnum*2 >= 0 && frontnum*2 <= 100000){
                q.push(frontnum*2);
                arr[frontnum*2] = arr[frontnum] + 1;
            }
        }
    }
    if(!q.empty())
        level = arr[q.front()];
    printf("%d\n", level);
}

N은 수빈이의 위치 K는 동생의 위치이다. 나는 이 문제를 풀면서 동생의 위치가 수빈의 위치보다 작을 수 있는 경우가 있을 것 같아 그 경우를 넣었다. 하지만 테스트케이스에서는 그러한 경우가 없는 것으로 확인이 된다. 이 문제가 BFS인 이유는 반복문 안에 queue를 사용해 탐색하기 때문이다. 수빈이가 이동하는 방법은 세가지인데 현재의 위치에서 +1, -1, *2를 해 이동하는 방법이다. 이동하는 횟수를 BFS의 level로 생각을 하면 이는 딱 들어맞게 된다.