백준 16397 탈출 Python 3

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

16397번: 탈출

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ16397.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys, math
from collections import deque
def press_btn():
    visit = [0]*100000
    visit[N] = 1
    q = deque([[N, 0]])
    while q:
        n, cnt = q.popleft()
        if n == G:
            print(cnt)
            return
        if cnt == T: continue
        if n+1 <= 99999 and not visit[n+1]:
            visit[n+1] = 1
            q.append([n+1, cnt+1])
        if 0 < n*2 <= 99999:
            new = n*2 - (10**int(math.log10(n*2)))
            if not visit[new]:
                visit[new] = 1
                q.append([new, cnt+1])
    print("ANG")

input = sys.stdin.readline
N, T, G = map(int, input().split())

press_btn()

---

풀이 과정

풀이 시간 16분

import sys, math
from collections import deque
def press_btn():
	#만든 숫자 방문 처리
    visit = [0]*100000
    visit[N] = 1
    q = deque([[N, 0]])
    
    while q:
        n, cnt = q.popleft()
        
        #G와 숫자가 같아지면 버튼 횟수를 출력하고 함수 종료
        if n == G:
            print(cnt)
            return
            
        #T번 버튼을 눌렀는데 G와 같지 않은 경우, 더이상 버튼을 누르지 않는다
        if cnt == T: continue
        
        #버튼 A 누르기
        if n+1 <= 99999 and not visit[n+1]:
            visit[n+1] = 1
            q.append([n+1, cnt+1])
            
        #버튼 B 누르기
        if 0 < n*2 <= 99999:
            new = n*2 - (10**int(math.log10(n*2)))
            if not visit[new]:
                visit[new] = 1
                q.append([new, cnt+1])
                
    #모든 경우의 수로 버튼을 눌렀는데도 G를 만들 수 없는 경우, 탈출 불가
    print("ANG")

input = sys.stdin.readline
N, T, G = map(int, input().split())

press_btn()

#시간복잡도 = O(V+E), 공간복잡도 = O(n)