[백준 16397번] [BFS] 탈출

Approach

잘 생각해보면 최대 T번 누를 수 있다는 명제를 T번 이동할 수 있다로 바꾸고, 버튼 A와 B를 누르고 나오는 숫자를 기준으로 생각해보면 비둘기집의 원리에 따라서 총 99999가지 경우의 수 밖에 없다. 따라서 해당 숫자들에 대해서 BFS를 돌려서 이 문제를 해결할 수 있다는 아이디어를 쉽게 떠올릴 수 있다.

 

A와 B 작동은 적당히 string과 int 사이를 왔다갔다 잘 변환시켜주면 된다. (stoi와 to_string을 잘 활용해주면 된다)

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

bool visited[100000];

int main(void){
    memset(visited, 0, sizeof(visited));
    fastio;
    string n, g;
    int t;
    cin >> n >> t >> g;

    queue<string> q;
    q.push(n);
    visited[stoi(n)] = 1;
    int move_num = 0;
    bool flag = false;

    while(true){
        if(move_num > t){
            cout << "ANG" << "\n";
            return 0;
        }
        int q_size = q.size();
        for(int i = 0; i < q_size; i++){
            string cur = q.front();
            q.pop();
            if(cur == g){
                flag = true;
                break;
            }

            if(stoi(cur) != 99999){
                if(!visited[stoi(cur) +1]){
                    q.push(to_string(stoi(cur) + 1));
                    visited[stoi(cur) + 1] = 1;
                }
            }
            if(stoi(cur) * 2 <= 99999){
                string temp = to_string(stoi(cur) * 2);
                for(int i = 0; i < temp.size(); i++){
                    if(temp[i] != '0'){
                        temp[i] = temp[i] - 1;
                        break;
                    }
                }
                if(!visited[stoi(temp)]){
                    q.push(to_string(stoi(temp)));
                    visited[stoi(temp)] = 1;
                }
            }
        }
        if(flag){
            cout << move_num << "\n";
            return 0;
        }
        move_num++;
    }
}