[C++] 백준 1697번: 숨바꼭질

 

dp문제인가 뭐지 했는데, BFS로 풀 수 있었다.

시작지점을 0으로 놓고, ranged-based for을 이용해서 cur-1, cur+1, cur*2를 방문하여 숫자를 하나씩 올려주었다.

 

#include <iostream>
#include <queue>
#define X first
#define Y second
using namespace std;

int dist[100002];
int n, k;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> k;
    fill(dist, dist + 100001, -1);
    dist[n] = 0;
    queue<int> Q;
    Q.push(n);
    
    while(dist[k] == -1){
        int cur = Q.front(); Q.pop();
        for(int c : {cur-1, cur+1, 2*cur}){
            if(c < 0 || c > 100000) continue;
            if(dist[c] != -1) continue;
            dist[c] = dist[cur] + 1;
            Q.push(c);
        }
    }
    cout << dist[k];
    
    return 0;
}