백준 13549번. 숨바꼭질 3(c++) / BFS

라인 기출문제?로 봤었던 문제인것 같다..!

아주 기본적인 BFS 문제이기 때문에 금방 풀 수 있었다.

다만, 조심해야하는 점은 순간이동에 걸리는 시간이 0초이기 때문에

+1, -1로 이동하는 것보다 순간이동으로 이동하는 코드가 먼저 나와야한다.

 

// 숨바꼭질3
#include <iostream>
#include <queue>
 
using namespace std;
 
int n, k;
int dx[2] = {-1, 1};
 
int hideAndSeek()
{
    queue<pair<int, int>> q;
    q.push(make_pair(n, 0));
    int visited[100001] = {0, };
    int ans = 0;
 
    while(!q.empty()){
        int x = q.front().first;
        int sec = q.front().second;
        q.pop();
        visited[x] = true;
 
        if(x==k){
            ans = sec;
            break;
        }
 
        // 순간 이동
        int nx = 2*x;
        if(0<=nx && nx<=100000 && !visited[nx]){
            visited[nx] = true;
            q.push(make_pair(nx, sec));
        }
 
        // 그냥 이동
        for(int i=0; i<2; i++){
            int nx = x+dx[i];
            if(0<=nx && nx<=100000 && !visited[nx]){
                visited[nx] = true;
                q.push(make_pair(nx, sec+1));
            }
        }
    }
 
    return ans;
}
 
int main()
{
    cin>>n>>k;
    cout<<hideAndSeek()<<"\n";
    return 0;
}