백준 1697 -숨바꼭질

문제 설명

 

 

<code>

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int N, K;
    cin >> N >> K ;
    
    int dist[100001]={0};
    bool check[100001];//갔다온지 확인하는 행렬
    
    queue<int> q;
    q.push(N);
    check[N] = true;
    
    while(!q.empty())
    {
        int now = q.front();
        
        if(now == K)
        {
            cout << dist[now]<<'\n';
            return 0;}
        q.pop();
        if(now-1 >= 0)
        {
            if(check[now-1] == false)
            {
                q.push(now-1);
                check[now-1]= true;
                dist[now-1] =dist[now] +1;
                
            }
        }
        
        if(now+1 <= 100001)
        {
            if(check[now+1] == false)
            {
                q.push(now+1);
                check[now+1]= true;
                dist[now+1] =dist[now] +1;
                
            }
        }
        
        if(now*2 <= 100001)
        {
            if(check[now*2] == false)
            {
                q.push(now*2);
                check[now*2]= true;
                dist[now*2] =dist[now] +1;
                
            }
        }
    }
  
    return 0;
}