1697번: 숨바꼭질

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


$O(l)$

각 정수 x마다 하나의 노드를 가지고 x-1,x+1,2*x와 연결된 간선이 있다고 생각한다. BFS탐색을 통해 최소비용을 구한다.
갈 수 있는 x 위치로는 200000까지 잡으면 되는데, 이보다 큰 x를 경유해서 목적지를 가는 것보다 1칸씩 이동해서 목적지에 도달하는 것이 항상 최선이기 때문이다.

#include<cstdio>
const int MXN = 1e5;
int n, k, c[MXN * 2], q[MXN * 2], h, t;
void f(int x) {
    if (x >= 0 && x < MXN * 2 && !c[x]) c[x] = c[q[h]] + 1, q[t++] = x;
}
int main() {
    scanf("%d %d", &n, &k);
    c[n] = 1;
    q[t++] = n;
    while (h^t) {
        f(q[h] - 1); f(q[h] + 1); f(q[h] * 2);
        h++;
    }
    printf("%d", c[k] - 1);
    return 0;
}