[백준] 1697. 숨바꼭질

문제

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

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

입력

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

출력

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

예제 입력

5 17

예제 출력

4

풀이

/* Date: 2020-08-29 */
#include <iostream>
#include <queue>
#define MAXN 100000

using namespace std;

typedef struct status{
    int loc;
    int sec;
} status;

queue<status> Q;
int is_visit[100001];
int N, K, Rst;

status get_status(int loc, int sec);

int main(){
    cin >> N >> K;
    is_visit[N] = 1;
    status init;
    init.loc = N; init.sec = 0;
    Q.push(init);

    while(!Q.empty()){
        status s = Q.front();
        Q.pop();
        if(s.loc == K){
            Rst = s.sec;
            break;
        }
        if(s.loc + 1 <= MAXN && !is_visit[s.loc + 1]){
            Q.push(get_status(s.loc + 1, s.sec + 1));
            is_visit[s.loc + 1] = 1;
        }
        if(s.loc - 1 >= 0 && !is_visit[s.loc - 1]){
            Q.push(get_status(s.loc - 1, s.sec + 1));
            is_visit[s.loc - 1] = 1;
        }
        if(s.loc * 2 <= MAXN && !is_visit[s.loc * 2]){
            Q.push(get_status(s.loc * 2, s.sec + 1));
            is_visit[s.loc * 2] = 1;
        }
    }
    cout << Rst << endl;
}

status get_status(int loc, int sec){
    status s;
    s.loc = loc;
    s.sec = sec;
    return s;
}