[백준] 숨바꼭질 3 (c++)

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

13549번: 숨바꼭질 3

풀이 방법

평범한 문제 처럼 보이지만 순간이동을 할 때에는 0초라는 재밌는 조건이 있다.

그래서 bfs할 때 그냥 queue를 사용하면 0초라는 조건 때문에 복잡하게 된다. (시간 많이 걸리는 경우를 먼저 q에서 pop 되는 경우 때문)

그래서 우선순위 queue를 사용해서 시간이 작게 걸리는 경우를 먼저 pop 하여 사용하면 문제를 해결할 수 있다.

#include <bits/stdc++.h>
using namespace std;

int N, K;
int visited[200001];

int bfs() {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, N));
    int next, ans;

    while(!q.empty()) {
        pair<int,int> cur = q.top();
        int t = cur.first;
        int now = cur.second;
        q.pop();
        visited[now] = 1;
        if (now == K) {
            ans = t;
            break;
        }
        if (now < K) {
            if (visited[now + 1] == -1) {
                q.push(make_pair(t + 1, now + 1));
            }
            if (now * 2 <= 200000 && visited[now * 2] == -1) {
                q.push(make_pair(t, now * 2));
            }
        }
        if (now - 1 >= 0 && visited[now - 1] == -1) {
                q.push(make_pair(t + 1, now - 1));
        }
    }
    return ans;

}
int main() {
    cin >> N >> K;
    memset(visited, -1, sizeof(visited));
    cout << bfs();
    return 0;
}