1697 숨바꼭질

문제 링크

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

풀이

수빈이의 현재 위치, 걸어서 갈 수 있는 X-1, X+1, 순간이동해서 갈 수 있는 2*X를 각각 하나의 노드로 생각하고 BFS를 실행하면 된다. 각 칸에 도착하는 데 걸린 시간들을 나타내는 배열 d를 선언하고, 새롭게 도착하게 된 칸에는 이전칸+1의 값을 넣어준다.(도착 시간 업데이트) 동생이 있는 위치 K에 도달하면 BFS를 종료하고 값을 출력한다.

C++ 코드

#include <iostream>
#include <queue>

using namespace std;

int d[100000];
int N, K;

void bfs(int N){
    queue<int> q;
    q.push(N);
    
    while(!q.empty()){
        N = q.front();
        if(N == K){cout<<d[N]<<endl; return;}
        q.pop();
        if(N+1<=100000 && d[N+1] == 0){q.push(N+1);d[N+1] = d[N]+1;}
        if(0<=N-1 && d[N-1] == 0){q.push(N-1);d[N-1] = d[N]+1;}
        if(2*N<=100000 && d[2*N] == 0){q.push(2*N);d[N*2] = d[N]+1;}
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin>>N>>K;
    bfs(N);
    
    return 0;
}