[개쉬운 풀이] 백준 1697 숨바꼭질 (9일차)

문제

생각

처음에는 단순하게 BFS로 갈 수 있는 모두의 경우를 계산하면 된다고 생각했다. 그러던 와중 우선순위 큐와 다익스트라를 활용하여 가장 빠른 시간을 구하는 것이 더 완벽하다고 생각했다.

따라서 다익스트라로 구현했지만, 실제 BFS와 비교해보니 단순 BFS로도 해결이 된다. (심지어 더빠름)

 

풀이

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int,int> ii;

const int MAX = 100001;

int N, K;
int isVisited[MAX];

void input(){
    cin >> N >> K;
    for(int i = 0; i < MAX; i++){
        isVisited[i] = MAX;
    }
}

bool process(int time, int next){
    if(time < isVisited[next]){
        isVisited[next] = time; 
        return true;
    }
    return false;
}

void sol(){
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    pq.push(make_pair(0, N));
    isVisited[N] = 0;

    while(!pq.empty()){
        ii cur = pq.top();
        pq.pop();
        int pos = cur.second;
        int cnt = cur.first;
        
        // move_forward
        if(pos+1 < MAX && process(cnt+1, pos+1)){
            pq.push(make_pair(cnt+1, pos+1));
        } 
        // move_behind
        if(pos-1 >= 0 && process(cnt+1, pos-1)){
            pq.push(make_pair(cnt+1, pos-1));
        } 
        // teleport
        if(pos*2 < MAX && process(cnt+1, pos*2)) { 
            pq.push(make_pair(cnt+1, pos*2));
        }
    }
    cout << isVisited[K] << endl;
}

int main(){
    input();
    sol();

    return 0;
}