백준 소스코드 [C++] 17071 숨바꼭질 5

www.acmicpc.net/problem/17071

17071번: 숨바꼭질 5

백준 소스코드 [C++] 17071 숨바꼭질 5

#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <cstdlib>
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define pli pair<ll, int>
#define make_unique(v) sort(all(v)), v.erase(unique(all(v), v.end())
typedef long long ll;
using namespace std;

int n,m;
bool chk[500001][2];

int bfs(){
    
    queue<int> q;
    q.push(n);
    chk[n][0]=true;
    int time=1;
    if(n==m) return 0;
    
    while(!q.empty()){
        int qSize = (int)q.size();
        m+=time;
        if(500000<m) return -1;
        
        for(int size = 0; size<qSize;size++){
            int here = q.front();
            int there;
            q.pop();
            
            for(int i=0;i<3;i++){
                
                if(i==0) there = here - 1;
                else if(i==1) there = here + 1;
                else there = here * 2;
                
                if(0<=there && there<=500000 && !chk[there][time%2]){
                    chk[there][time%2]=true;
                    q.push(there);
                }
            }
        }
        
        if(chk[m][time%2])  return time;
        time++;
    }
    
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>n>>m;
    cout<<bfs()<<'\n';

    return 0;
}