백준 16397번 : 탈출 C++

BOJ 16397번 탈출 문제

2018 홍익대학교 컴퓨터공학과 코딩대회 D번 문제이다.

또 문제를 잘 못 봤다. 제일 높은 자리수 1을 빼는게 각 자리를 비교해서 가장 큰 수를 뺴는 걸로 생각했다.

왜 더 어렵게 생각해서 구현도 복잡하고 시간도 더 낭비했는지..

이런 것도 다 실력이니 이런 실수를 줄이는 노력을 해야겠다.

문제는 BFS로 풀면 된다.

16397.cpp

#include <bits/stdc++.h>
using namespace std;
bool visited[100000];
int po(int n) {
    int nn = 1;
    for (int i = 0; i < n; i++) {
        nn *= 10;
    }
    return nn;
}
int B(int i) {
    if (i == 0) {
        return i;
    }
    int originI = i * 2;
    i = originI;
    int t = 0;
    while (i > 0) {
        t++;
        i /= 10;
    }
    originI -= po(t - 1);
    return originI;
}

int main() {
    int n, t, g;
    cin >> n >> t >> g;
    queue<pair<int, int> > q;
    visited[n] = true;
    q.push({n, 0});

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

        if (cnt > t) {
            cout << "ANG";
            return 0;
        }
        if (now == g) {
            cout << cnt;
            return 0;
        }

        if ((now + 1 <= 99999) && !visited[now + 1]) {
            q.push({now + 1, cnt + 1});
            visited[now + 1] = true;
        }
        int next = B(now);
        if ((now * 2 <= 99999) && !visited[next]) {
            q.push({next, cnt + 1});
            visited[next] = true;
        }
    }
    cout << "ANG";
}