[ 16397 ] [ BFS ] 탈출

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

16397번: 탈출

---

풀이 과정

---

1. 초기 현재 값과 단계를 큐에 넣은 다음, BFS를 진행한다.
   1. 다음 단계의 값에 일단 i+1을 넣어준다. -> 버튼 A
   2. 버튼 B를 구현할 때, 현재 단계의 값이 0이거나 입력받은 값을 2배한 값이 99999보다 크다면 버튼 B를 누를 수 없는 것이므로 버튼 A를 누른 결과만 진행한다.
   3. 아니라면, 2를 곱한 값의 가장 앞자리의 숫자를 하나 줄여주어야 하므로 1 * 10^(전체 자릿수-1)를 빼준다.
      • 예를 들면, 4자리라면 1000을 빼준다. 
2. 큐가 비게 되거나, 단계가 T를 넘어가게 되면 "ANG"를 출력해 주고, 목표한 값에 도달한다면 현재 단계를 출력시켜 준다.

---

소스 코드

---

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N, T, G = map(int, input().split())
queue = deque()
queue.append([N, 0])

def get_next_number(i):
    temp = i * 2
    if i == 0 or temp > 99999:
        return [i+1]
    index = 1
    while temp//10 != 0:
        temp //= 10
        index *= 10
    
    return [i+1, i * 2 - index]

visited = set()
visited.add(N)

while queue:
    target, step = queue.popleft()
    if step == T+1:
        print("ANG")
        break
    if target == G:
        print(step)
        break
    for nx in get_next_number(target):
        if nx not in visited:
            queue.append([nx, step+1])
            visited.add(nx)
else:
    print("ANG")