[BaekJoon] 1697번 : 숨바꼭질

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

풀이

• BFS를 활용하는 문제인데 2차원이 아닌 1차원으로 작성하면 됩니다.

#include<iostream>
#include<queue>
using namespace std;

int arr[100005];

int main(){
    int n,k;
    cin>>n>>k;
    
    queue<int> q;
    arr[n] = 1;
    q.push(n);
    
    while(!q.empty()){
        int cur = q.front();
        if(cur == k) break;
        q.pop();
        
        if(cur>0 && arr[cur-1] == 0){
            q.push(cur-1);
            arr[cur-1] = arr[cur]+1;
        }
        
        if(cur<100000 && arr[cur+1] == 0){
            q.push(cur+1);
            arr[cur+1] = arr[cur]+1;
        }
        
        if(cur<=50000 && arr[2*cur] == 0){
            q.push(2*cur);
            arr[2*cur] = arr[cur]+1;
        }
    }
    cout<<arr[k]-1;
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.