[C++] 백준 1697 숨바꼭질

 
#include <iostream>
#include <algorithm>
#include <memory>
#include <queue>
#include <tuple>
 
int N = 0;
int K = 0;
std::queue<int> que = {};
int visit[100001] = {};
 
bool QuePush(int iStart, int iDist)
{
    if (iDist >= 0 && iDist <= 100000)
    {
        if (visit[iDist] != 100000)
            return false;
 
        visit[iDist] = visit[iStart] + 1;
 
        if (iDist == K)
        {
            std::cout << visit[iDist];
            return true;
        }
 
        que.push(iDist);
    }
 
    return false;
}
 
int main()
{
    std::cin >> N >> K;
 
    if (K <= N)
    {
        std::cout << N - K;
        return 0;
    }
 
    for (int i = 0; i <= 100000; ++i)
    {
        visit[i] = 100000;
    }
 
    visit[N] = 0;
 
    que.push(N);
 
    while (!que.empty())
    {
        int iStart = que.front();
 
        que.pop();
 
        int iDist = iStart + 1;
        if (QuePush(iStart, iDist))
            return 0;
 
        iDist = iStart - 1;
        if (QuePush(iStart, iDist))
            return 0;
 
        iDist = iStart * 2;
        if (QuePush(iStart, iDist))
            return 0;
    }
 
    return 0;
}
 

BFS, 더해가면서 풀면 바로 답을 낼 수 있다.

i <= N 처리를 안해서 뭐가 틀렸는지 찾느라 오래걸렸다.