greentea31's Note

https://www.acmicpc.net/problem/1697

풀이 과정

현재 N에 있고, 동생이 K에 있을 때, 하루마다 현재 점에서 +1, -1, *2로 이동이 가능한데, 동생을 찾는 가장 빠른 시간을 구하는 문제이다.

BFS로 +1, -1, *2 이동해보면서 원점으로 부터의 거리를 계산하고, K일때 원점에서의 거리를 출력해주면 된다. 동생이 10만까지만 위치 가능하긴 해도, 수빈이는 10만을 넘어선 점에 위치가 가능하긴 한데 이 문제에서는 10만을 넘어가면 무조건 원점과 10만까지의 거리보다 더 많은 거리를 이동해야 하므로 고려해주지 않아도 된다.

소스 코드

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int d[100001];

    for (int &i : d) {
        i = -1;
    }

    queue<int> Q;

    int N, K;
    cin >> N >> K;

    d[N] = 0;
    Q.push(N);

    while(!Q.empty()) {
        int cur = Q.front(); Q.pop();
        if (cur == K) {
            cout << d[K];
            return 0;
        }

        for (int next : {cur-1, cur+1, 2*cur}) {
            if (next < 0 || next > 100000) continue;
            if (d[next] != -1) continue;
            d[next] = d[cur] + 1;
            Q.push(next);
        }
    }

    return 0;
}