백준 16397번 탈출 C++

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

16397번: 탈출

 

bfs

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, t, g;
vector<bool> found;

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

   cin >> n >> t >> g;
    found = vector<bool>(100000, false);

    queue<pair<int,int>> q;
    q.push({ n,0 });
    found[n] = true;

    int ans = -1;

    while (!q.empty()) {
        auto curr = q.front();
        int currVal = curr.first;
        int currCnt = curr.second;
        if (currVal == g) {
            ans = currCnt;
            break;
        }
        q.pop();

        {
            int nextVal = currVal * 2;
            if (nextVal < 100000 && nextVal != 0) {
                string str = to_string(nextVal);
                str[0] = str[0] - 1;
                nextVal = stoi(str);
                if (found[nextVal] == false && currCnt < t) {
                    found[nextVal] = true;
                    q.push({ nextVal,currCnt + 1 });
                }
            }
        }
        {
            int nextVal = currVal + 1;
            if (nextVal < 100000) {
                if (found[nextVal] == false && currCnt < t) {
                    found[nextVal] = true;
                    q.push({ nextVal,currCnt + 1 });
                }
            }
        }
    }

    if (ans == -1) cout << "ANG";
    else cout << ans;
}