[boj] 백준 13549 숨바꼭질 3 (c++) - BFS

[문제]

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

13549번: 숨바꼭질 3

 

[풀이]

우선순위 큐를 이용한 BFS 문제. 

x+1, x-1로 이동할 때는 시간이 1초가 들고, 2*x로 이동할 때는 0초가 든다. 즉 간선의 가중치가 다르기 때문에 다익스트라 문제로 볼 수 있고, 우선순위 큐를 이용한다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <math.h>
#define INF 987654321

using namespace std;

int n, k;
bool visited[100001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k; //수빈이 위치, 동생 위치

    priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

    pq.push({0, n});

    while(!pq.empty()){
        int time = pq.top().first;
        int loc = pq.top().second;
        visited[loc] = true;
        pq.pop();

        if(loc==k){
            cout << time;
            break;
        }

        if(loc+1 <= 100000 && !visited[loc+1]){
            pq.push({time+1, loc+1});
        }
        if(loc-1 >= 0 && !visited[loc-1]){
            pq.push({time+1, loc-1});
        }
        if(loc*2 <= 100000 && !visited[loc*2]){
            pq.push({time, loc*2});
        }
    }


}