(C++) - 백준(BOJ) 13549번 : 숨바꼭질 3

www.acmicpc.net/problem/13549

13549번: 숨바꼭질 3

bfs문제였습니다.

 

풀이방법

 1. 순간이동하는데에 cost가 들지 않기 때문에 먼저 10만 이전까지 순간이동을 해보는 것이 유리합니다. 따라서 우선순위를 주기 위해 bfs실행시 priority queue를 사용합니다.

 

 2. bfs를 시행합니다. 시행시 다음 이동할 곳이 범위를 초과하면 안되므로 조건부 push를 해줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int ck[100001],n,k;
priority_queue <pii,vector<pii>,greater<pii>> pq;
int bfs(){
    if(n>k) return n-k;
    int ans = 0x3f3f3f3f;
    pq.push({0,n});
    ck[0] = 1;
    
    while(!pq.empty()){
        int x = pq.top().second;
        int sec = pq.top().first;
        pq.pop();
        if(x == k) return sec;
        if(x*2 <= 100000 && !ck[x*2]){
            ck[x*2] = 1;
            pq.push({sec,x*2});
        }
        if(x+1 <= 100000 && !ck[x+1]){
            ck[x+1] = 1;
            pq.push({sec+1,x+1});
        }
        if(x-1 >= 0 && !ck[x-1]){
            ck[x-1] = 1;
            pq.push({sec+1,x-1});
        }
    }
}

int main(){
    cin >> n >> k;
    cout << bfs();
}