[백준/C,C++] 1697번: 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

풀이

경우의 수가 1을 뺀다, 더한다, 2를 곱한다. 3가지입니다.

 

3가지의 경우를 BFS로 탐색하며 결괏값과 일치하는 경우 깊이를 출력해주면 됩니다.

 

#include<iostream>
#include<queue>

using namespace std;

const int MAX = 100001;

int n, k;
queue<int> q;
int depth[MAX];

int move(int n, int way)
{
    if (way == 0) return n - 1;
    else if (way == 1) return n + 1;
    else return n * 2;
}

bool check(int n)
{
    if (n >= 0 && n <= 100000) {
        if (depth[n] == 0) return true;
    }
    return false;
}

void BFS()
{
    q.push(n);
    depth[n] = 1;
    while(!q.empty()) {
        int pre = q.front();
        q.pop();
        for (int i = 0; i < 3; i++) {
            int next = move(pre, i);
            if (check(next)) {
                q.push(next);
                depth[next] = depth[pre] + 1;
                if (next == k) return;
            }
        }
    }
}

int main(void)
{
    cin >> n >> k;

    BFS();

    cout << depth[k] - 1;

    return 0;
}

반례

Input

1 10

Output

4

 

Input

2555 59999

Output

686

 

Input

99999 9

Output

99990

 

Input

0 100000

Output

22