[ 1038 ] [ BFS ] 감소하는 수

문제 설명

---

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

---

풀이 과정

1. [1~9]까지의 값을 미리 큐에 넣어둔 다음 BFS를 진행한다.
   • N = 0일때는 따로 예외로 처리해주어야 함.
   • 현재 값을 N이라고 할 때, N의 맨 마지막 자리 숫자보다 작은 숫자들을 뒤에 붙여서 큐에 다시 넣어준다.
   • 예시로 N이 2라고 할때, 20, 21을 큐에 넣어준다.
2. BFS를 진행하면서 큐가 비게 되면 N번째 감소하는 수는 만들 수 없는 것이므로 -1 리턴
   • 큐에서 뺀 수가 N번째 숫자면 해당 수 리턴

---

소스 코드

---

import sys
from collections import deque

N = int(input().rstrip())

def bfs(N):
    queue = deque([i for i in range(1, 10)])
    count = 0

    while queue:
        t1 = queue.popleft()
        count += 1
        if count == N:
            return t1
        dest = int(str(t1)[-1])
        for i in range(dest):
            queue.append(int(str(t1) + str(i)))

    return -1

if N == 0:
    print(0)
else:
    print(bfs(N))