문제

13549번: 숨바꼭질3

풀이

순간이동 할 때와 걷을 때의 시간이 다르기 때문에 우선순위 큐를 사용해야한다.
다익스트라 알고리즘을 활용하여 문제를 해결할 수 있고
일반적인 bfs 알고리즘에 우선순위 큐를 사용하여 해결 할 수 있다.

bfs로 해결 가능한 이유는 이 문제가 특별하기 때문이다

• 순간이동의 경우를 먼저 우선 순위 큐에 넣는다면 걷기로 이동하는 경우가 순간이동 하는 경우보다 먼저 큐에서 pop 될 수 없다.

코드

bfs

#include<iostream>
#include<queue>
#include<vector>

#define Node pair<int, int>

using namespace std;

const int MAX = 100001;
vector<bool> visited;
int n, k;
int answer;

void bfs(){
    priority_queue< Node, vector<Node>, greater<Node> > q;
    q.emplace(0,n);
    visited[n] = true;
    while (!q.empty()){
        int time = q.top().first;
        int cur = q.top().second;
        q.pop();
        if(cur == k){
            answer = time;
            return;
        }
        int next;
        
        next = cur * 2;
        if(next < MAX && !visited[next]){
            q.emplace(time, cur*2);
            visited[cur*2] = true;
        }
        next = cur + 1;
        if(next < MAX && !visited[next]){
            q.emplace(time+1, cur+1);
            visited[cur+1] = true;
        }
        next = cur - 1;
        if(next >= 0 && !visited[next]){
            q.emplace(time+1, cur-1);
            visited[cur-1] = true;
        }
    }
}

int main(){
    visited.assign(MAX, false);

    cin >> n >> k;
    bfs();
    cout << answer << endl;

    return 0;
}

다익스트라

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>


using namespace std;

int n, k;
const int MAX = 100001;
vector<int> dist;

void dijkstra(){
    dist[n] = 0;
    priority_queue< pair<int, int> > pri_q;
    pri_q.emplace(-dist[n], n);
    while(!pri_q.empty()){
        int v = pri_q.top().second;
        int t = -pri_q.top().first;
        pri_q.pop();

        if(t <= dist[v]){
            if(v*2 < MAX && t < dist[v*2]){
                dist[v*2] = t;
                pri_q.emplace(-dist[v*2], v*2);
            }
            if(v+1 < MAX && t+1 < dist[v+1]){
                dist[v+1] = t+1;
                pri_q.emplace(-dist[v+1], v+1);
            }
            if(v-1 >= 0 && t+1 < dist[v-1]){
                dist[v-1] = t+1;
                pri_q.emplace(-dist[v-1], v-1);
            }
        }
    }

    return;
}

int main(){
    cin >> n >> k;
    dist.assign(MAX, 100001);
    dijkstra();
    cout << dist[k] << endl;

    return 0;
}