백준1174 - 줄어드는 숫자

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

15729번: 방탈출

bfs를 이용하여 내림차순으로 구성되있는 수를 찾아내는 문제다. 처음에 0~9까지의 수를 큐에 넣어주고 현재 수의 일의자릿수 보다 작은 수가 있으면 탐색해나가는 형식으로 구현하였다. 숫자가 커질수 있어서 long long int를 사용하였다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N;
int limit;
vector<long long int> v;

void bfs() {
    int cnt = 0;
    queue<long long int> q;
    for(long long int i = 0; i <= 9; i++) {
        q.push(i);
        v.push_back(i);
        cnt++;
    }
    
    while(!q.empty()) {
        long long int x = q.front();
        q.pop();
        
        int start = x % 10 - 1;
        
        for(int i = start ; i >= 0; i--) {
            long long int temp = x * 10 + i;
            q.push(temp);
            v.push_back(temp);
            cnt++;
        }
    }
}


int main() {
    cin >> N;
    
    bfs();
    
    sort(v.begin(), v.end());
    
    if(N > 1023) {
        cout << -1;
    }
    else {
        cout << v[N - 1];
    }
    
    return 0;
}