[ 백준 16397 ] 탈출 (C++)

백준의 탈출(16397) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 현재 숫자에서 2가지 방법으로 주어진 목표 숫자를 최소 몇번만에 만들 수 있는지 구하는 문제이다.

   본인은 이 문제를 너비우선탐색(BFS)로 접근해 보았다.

   탐색을 진행할 때, 주어진 횟수인 T번만큼 이미 탐색을 했는데도 답이 안나왔을 경우에는 그 다음 탐색으로

   넘어가도록 만들어 주었다. 왜냐하면 T번 이상 탐색을 하는 것은 의미가 없기 때문에, 아직 T번 이하의 값들이 저장되어

   있는 그 다음 큐의 원소들로 넘어가도록 구현해 주었다.

   이 외에, 특별히 주의해야할 부분은 없었던 문제인 것 같다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<string>
 
#define endl "\n"
#define MAX 100000
using namespace std;
 
int N, T, G;
bool Visit[MAX];
 
void Input()
{
    cin >> N >> T >> G;
}
 
int Button_B(int Num)
{
    int R = Num * 2;
    if (R >= MAX) return R;
 
    string S = to_string(R);
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] != 0)
        {
            int Temp = S[i] - '0';
            Temp--;
            S[i] = Temp + '0';
            break;
        }
    }
    R = stoi(S);
    return R;
}
 
void Solution()
{
    queue<pair<int, int>> Q;
    Q.push(make_pair(N, 0));
    Visit[N] = true;
 
    while (Q.empty() == 0)
    {
        int Cur = Q.front().first;
        int Cnt = Q.front().second;
        Q.pop();
 
        if (Cur == G)
        {
            cout << Cnt << endl;
            return;
        }
        if (Cnt == T) continue;
 
        int Next = Cur + 1;
        if (Next < MAX && Visit[Next] == false)
        {
            Visit[Next] = true;
            Q.push(make_pair(Next, Cnt + 1));
        }
 
        if (Cur != 0)
        {
            Next = Button_B(Cur);
            if (Next < MAX && Visit[Next] == false)
            {
                Visit[Next] = true;
                Q.push(make_pair(Next, Cnt + 1));
            }
        }
    }
    cout << "ANG" << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}