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

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

1697번: 숨바꼭질

간단한 bfs문제이다.

큐에는 방문하는 숫자정보와 누적 방문  횟수를 저장해주면 된다.

그리고 현재 방문하는 숫자 - 1, 숫자 + 1, 숫자 x 2를 방문해주면 된다. 총 3가지 경우에 대해 모두 방문해보는 것이다. 

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int n,k,ans;
queue<pair<int,int>> q;
bool visited[200001];

void bfs(){
    while (!q.empty()) {
        int num = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if (num == k) {
            ans = cnt;
            break;
        }

        if (num-1 >= 0 && num-1 < 100001 && !visited[num-1]){
            visited[num-1] = true;
            q.push({ num - 1, cnt + 1 });
        }
        if (num+1 >= 0 && num+1 < 100001 && !visited[num+1]){
            visited[num+1] = true;
            q.push({ num + 1, cnt + 1 });
        }
        if (num*2 >= 0 && num*2 < 100001 && !visited[num*2]){
            visited[num*2] = true;
            q.push({ num *2, cnt + 1 });
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;
    q.push({n,0});
    visited[n]= true;
    bfs();

    cout << ans;
    return 0;
}