BOJ 1697번 :: 숨바꼭질

#문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

 

#작성 코드

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
 
int N, K;
bool visit[100001];
int sec=0;
queue<int> q;
 
void input(){
    // 수빈이 위치 N, 동생 위치 K를 입력받는다. 
    scanf("%d %d", &N, &K);
}
 
int solve(){
    q.push(N);
    visit[N] = true;
    if (K<=N){
        return N-K;
    } 
    while(!q.empty()){
        sec++;
        int size = q.size();
        for(int i=0; i<size; i++){
            int now = q.front();
            q.pop();
            
            // x-1, x+1, x*2를 체크한다. 
            int check[3] = {now-1, now+1, now*2};
            for(int i=0; i<3; i++)
                // 새 위치가 범위 내에 존재하면 방문하지 않은곳 방문. 
                if( check[i] >=0 && check[i]<=100000){
                    if( visit[check[i]]==true ) continue;
                    visit[check[i]] = true;
                    // 새 위치에서 동생을 만난다면 걸린 시간 리턴! 
                    if( check[i] == K ) return sec;
                    q.push(check[i]);
                }
        }
    }
}
 
int main(){
    input();
    cout<< solve();
    return 0;
}

##