[백준] 1694 숨바꼭질

 

BFS를 잘 활용하면 되는 문제.

그래프를 잘 생각 해보자.

각 숫자들을 그래프의 노드라고 했을 때,

1만큼 떨어진 이웃하는 숫자는 양방향 간선으로 다 이어져 있고,

x노드에서 2x노드로 가는 간선들이 있다.

BFS는 모든 정점과 간선을 살펴보는 알고리즘이므로 시간복잡도는 O(|V| + |E|)인데,

V = 100,000, E < 300,000 이면 충분할 거라고 생각했다.

 

참고로 memset에 사이즈를 sizeof(d)/sizeof(int) 라고 했다가.... 수없이 실패를 했던 문제이다.

나머지는 최단거리를 구하는 BFS문제로 직관적으로 쉽게 풀 수 있다.

  

    
    
    
    
  
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;

int d[100001];

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(n);
    d[n] = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        if (u == k) break;

        int v = u + 1;
        if (v <= 100000 && d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }

        v = u - 1;
        if (v >= 0 && d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }

        v = 2 * u;
        if (v <= 100000 && d[v] == -1) {
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
    printf("%d\n", d[k]);
    return 0;
}