[백준/16397/파이썬] 탈출

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

16397번: 탈출

Problem

홍익이는 최대 T회 버튼을 누를 수 있고, 그 횟수 안에 LED로 표현된 N을 G와 같게 만들어야 탈출할 수 있다.

홍익이는 최소한의 횟수로 버튼을 눌러 탈출하려고 한다.

 

조건

1. 버튼 A를 누르면, N이 증가한다.
2. 버튼 B를 누르면, N이 2가 곱해진 뒤, 0이 아닌 가장높자릿수의 숫자가 1 줄어든다. 예를들어, 123 -> 246->146 .  5->10->0 의 계산과정을 거친다.
3. LED가 다섯 자리까지밖에 없기 때문에 N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
4. 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.
5. 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다.

SOL)

 

이것도, 최소한의 입력을 입력하면서, 어떤 특정조건을 클리어해야하는 문제이다.

즉, 최단거리를 탐색할 수 있는 방법은 엄 ~청 많다.그 중에 하나인 BFS를 이용해서, 해당 문제를 접근하면 된다.

탐색하는게 2차원 board인건 우리가 많이 풀어봤는데, 이렇게도 응용이 가능하다는걸 보여주는 문제이다.

BFS는 완전탐색 알고리즘 중 하나이며, 그 중에서도 최단거리를 알아낼 수 있는 알고리즘이란걸 잊으면 안됨!

 

# btnA = n +1 
# btnB = 2*n , 가장 큰 자릿수가 1 감소. 10 이면 , 0 , 단, 0이면 변하지않음.
# N이 99,999를 넘어가는 순간 탈출에 실패하게 된다.
# 버튼 B를 눌러 N에 2를 곱한 순간 수가 99,999를 넘어간다면, 
# 높은 자릿수의 수를 1 낮췄을때 99,999를 넘지 않는다고 해도 탈출에 실패하게 된다.
# 최대 T번, LED로 표횐된 N을 G와 같게 만들어야함. 
# 최소한의 버튼 입력으로, 방을 탈출해야함. 
import sys
from math import log10
from collections import deque
input = sys.stdin.readline

def calA(n):
    return n+1

def calB(n):
    if n == 0:
        return 0
    n *= 2
    if n > 99999:
        return -1
    d = int(log10(n)) # 최대 자릿수를 d라고함. 최대 자릿수 -1 이므로, n-10**d이다.
    return n - 10 ** d 
def solve():
    global minAns
    q = deque()
    q.append([N, 0])
    check[N] =1
    while q:
        num, cnt = q.popleft()
        if cnt > T:
            break
        if num == G:
            minAns=min(minAns,cnt)
            continue
        btnA=calA(num)
        btnB=calB(num)
        for nextNum in (btnA,btnB):
            if 0 <= nextNum <= 99999 and check[nextNum] == 0:
                q.append([nextNum, cnt+1])
                check[nextNum] = 1

check = [0 for _ in range(100000)]
N, T, G = map(int, input().split())

minAns = T+1
solve()
print(minAns if minAns != T+1 else "ANG")