백준 13549번, 숨바꼭질 3(C, C++)

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

13549번: 숨바꼭질 3

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

using namespace std;

bool visited[100001];


int BFS(int X, int K){
 
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, X));
    visited[X] = true;
    

    while(!q.empty()){
        int cur = q.top().second;
        int count = q.top().first;
        q.pop();
 
        if(cur == K){
            return count;
        }

        if(cur * 2 <= 100000 && !visited[cur * 2]){
            visited[cur * 2] = true;
            q.push(make_pair(count, cur * 2));
        }

        if(cur + 1 <= 100000 && !visited[cur + 1]){
            visited[cur+1] = true;
            q.push(make_pair(count + 1, cur + 1));
        }
        if(cur - 1 >= 0 && !visited[cur - 1]){
            visited[cur -1] = true;
            q.push(make_pair(count + 1, cur - 1));
        }
    }     
}


int main(void){
    int N;
    int K;
    cin>>N>>K;

    cout<<BFS(N, K)<<endl;
    return 0;
}

BFS를 통해 현재 위치 X에서 +1, *2, -1을 하는 3가지 방식으로 이동하는 것을 BFS로 구현하였다.

다만 우리가 주의할 점은 1에서 2로 간다고 해봅시다.

그러면 가는 방식은 BFS에서 '1' -> '1' + '1' = '2' 로 가는 방법과 1 -> 1 * 2 = 2 = 2로 가는 방법이 있습니다.

제일 첫 번째 방법은 1초의 시간이 걸리고 두 번째 방식은 0초의 시간이 걸립니다.

queue에 담겨진 시간과 위치 정보에 대한 이동 if문들은 우선순위가 필요해보입니다.

왜냐하면 만약에 BFS에서 visited[2]가 1+1 방식으로 true가 되었다면,  1*2 방식은 if(!visited[2])아니기 때문에,

실행할 수 없기 때문입니다.

저희는 최소한의 시간으로 가는 것을 목적으로 두기 때문에 순간이동하는 방식을 우선으로 둬야합니다.

1초로 가는 방법보단 0초로 가는 방법을 택하는게 맞는 판단이겠지요.

3가지 if문 중에서 제일 상단에 배치합니다. 다른 이동 방법때문에 방문처리 배열이 true가 되어  순간이동 if문의 방문처리 조건이 성립되지 않을 수 있습니다.

 

그리고 우선순위 큐를 사용하여 0초로 순간이동하는 것을 우선으로 만듭니다.

원래 BFS는 가중치가 동일하다는 것을 가정 하에 출발하는 것인데, 어찌보면 이 문제는 다익스트라 알고리즘으로 봐도 무방하다 생각합니다.