BOJ 16397 - 탈출

문제

백준 온라인 저지 - 16397번

풀이 과정

BFS 를 통해 목표 숫자에 도달하기 위한 최소 버튼 횟수를 구하는 문제입니다.

각각의 버튼을 누를 수 있는 조건이 주어져 있으므로 이를 기준으로 탐색을 수행하면됩니다.
숫자에 대한 연산(맨 앞자리 감소)은 Python의 슬라이싱을 활용하면 쉽게 구현할 수 있습니다.

코드

import sys
from collections import deque


N, T, G = list(map(int, sys.stdin.readline().split()))
INF = 100000


def bfs(start):
    q = deque()
    visit = [0 for _ in range(INF)]
    q.append((start, 0))
    visit[start] = 1

    while q:
        here, cost = q.popleft()
        if cost > T:
            return 'ANG'
        if here == G:
            return cost

        # A 버튼을 누른 경우
        if here+1 < INF and not visit[here+1]:
            q.append((here+1, cost+1))
            visit[here+1] = 1

        # B 버튼을 누른 경우
        if here*2 < INF:
            temp = str(here*2)
            if int(temp) != 0:
                temp = str(int(temp[0])-1) + temp[1:]
            if not visit[int(temp)]:
                q.append((int(temp), cost+1))
                visit[int(temp)] = 1

    return 'ANG'


def solution():
    ans = bfs(N)
    return ans


print(solution())