[백준] 16397번 탈출

💡문제접근

• BFS 탐색을 이용해 해결할 수 있는 문제였다.

💡코드(메모리 : 36388KB, 시간 : 136ms)

import sys
input = sys.stdin.readline
from collections import deque
import math

N, T, G = map(int, input().strip().split())

def bfs(start):
    queue = deque()
    queue.append([start, 0])
    visited = [0] * 100000
    visited[start] = 1
    while queue:
        v, cnt = queue.popleft()
        # 최대 T회 버튼을 누를 수 있으므로 T회를 초과하면 탈출 불가
        if cnt > T:
            return "ANG"

		# Queue에서 뽑은 숫자 v와 G가 같다면 탈출
        if v == G:
            return cnt

        # 버튼 A를 누르는 경우
        if v + 1 <= 99999 and not visited[v + 1]:
            visited[v + 1] = 1
            queue.append([v + 1, cnt + 1])

        # 버튼 B를 누르는 경우
        # 그런데 가장 높은 자릿수를 1만큼 감소하기 전에 만약 두 배 곱한 값이 이미 99,999를 넘어선다면 실패하므로 두 배 곱한 값의 범위를 0 ≤ v × 2 ≤ 99,999로 설정함
        if 0 < v * 2 <= 99999:
            nv = v*2 - (10**int(math.log10(v*2)))	# 가장 높은 자릿수를 1만큼 감소
            if not visited[nv]:
                queue.append([nv, cnt + 1])
                visited[nv] = 1
    return "ANG"

ans = bfs(N)
print(ans)

💡소요시간 : 40m