백준 13549 숨바꼭질 3

bfs는 모든 가중치가 1일 때 가능하다.

앞서 풀었던 숨바꼭질 문제는 수빈이가 이동할 때 모두 1초가 걸렸기 때문에 가능했다.

하지만 이번 문제는 0초에 이동할 수 있어서 가중치가 0인 경우가 있다.

 

원래 bfs는 queue에 넣는 건데, 다 가중치가 1이기 때문에 거리가 1일 때, 거리가 2일 때 차곡차곡 쌓인다.
하지만 가중치가 다르면 꺼냈을 때 값이 뒤죽박죽이 된다. 

이럴 경우에 queue를 여러 개 사용해서 푼다.

즉, 0초 일 때 넣을 queue와 1초 일 때 넣을 queue 총 2개를 사용해서 문제를 푼다.

#include <iostream>
#include <queue>
#include <deque>
using namespace std;
bool c[1000000];
int d[1000000];
int MAX = 1000000;
int main() {
    int n, m;
    cin >> n >> m;
    c[n] = true;
    d[n] = 0;
    queue<int> q;
    queue<int> next_queue;
    q.push(n);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now*2 < MAX) {
            if (c[now*2] == false) {
                q.push(now*2);
                c[now*2] = true;
                d[now*2] = d[now];
            }
        }
        if (now-1 >= 0) {
            if (c[now-1] == false) {
                next_queue.push(now-1);
                c[now-1] = true;
                d[now-1] = d[now] + 1;
            }
        }
        if (now+1 < MAX) {
            if (c[now+1] == false) {
                next_queue.push(now+1);
                c[now+1] = true;
                d[now+1] = d[now] + 1;
            }
        }
        if (q.empty()) {
            q = next_queue;
            next_queue = queue<int>();
        }
    }
    cout << d[m] << '\n';
    return 0;
}