[boj] 우선 순위가 있는 bfs

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

bfs를 이용한 숨바꼭질 문제의 경우 문제를 푸는 방식은 항상 정해져있었다.
따라서 원래 구현하는대로 코드를 짰더니, 1 2에서 0이 아닌 1이 출력 됨을 확인할 수 있었다.

숨바꼭질3 문제의 경우 순간이동 시 0초가 걸리므로 순간이동의 우선순위가 더 높다.
따라서 우선순위 큐 혹은 덱을 사용해 순간이동하는 경우는 front로 넣어주어야 한다.

#include <iostream>
#include <deque>
using namespace std;
int n, k;
bool visited[200001];

int main() {
    cin >> n >> k;
    deque<pair<int, int> > q;

    q.push_back(make_pair(n, 0));
    visited[n] = true;

    pair<int, int> front;
    while (!q.empty()) {
        front = q.front();
        q.pop_front();
        if (front.first == k) {
            cout << front.second;
        }

        if (front.first * 2 < 200001 && !visited[front.first * 2]) {
            visited[front.first * 2] = true;
            q.push_front(make_pair(front.first * 2, front.second));
        }
        if (front.first + 1 < 200001 && !visited[front.first + 1]) {
            visited[front.first + 1] = true;
            q.push_back(make_pair(front.first + 1, front.second + 1));
        }
        if (front.first - 1 >= 0 && !visited[front.first - 1]) {
            visited[front.first - 1] = true;
            q.push_back(make_pair(front.first - 1, front.second + 1));
        }
    }
}

처음에 queue로 풀었다가 덱으로 고친거라 deque인데 q로 되어있다..