[BOJ] 16397. 탈출

문제

숨바꼭질 (https://www.acmicpc.net/problem/1697)

풀이

1. 초기 접근

• 문제조건 해석
  • 움직임, 경로에 대한 문제고, 간선의 길이가 1로 정해져있다.
    • BFS 문제다.
• 알고리즘
  • 전체적으로 1697.숨바꼭질 과 동일한 문제다.
  • 다만, 여기서 신경써야할 부분은, 버튼 B를 누르면 N에 2가 곱해진 뒤, 0이 아닌 가장 높은 자릿수의 숫자가 1 줄어든다. 이 부분이다.
    • 언어에 따라 다르게 처리할 수 있겠지만, 파이썬은 그래도 str() 이나 int() , .join() 을 통해 쉽게 처리할 수 있다. 아래 코드를 보면 된다.
• 코드

import sys

n, t, g = list(map(int, sys.stdin.readline().split()))

def bfs(n, t, g):
    q, visited = [n], {n}
    step = 0
    while q:
        size = len(q)

        for i in range(size):
            cur = q.pop(0)
            if cur == g:
                return step

            if cur*2 > 99999:
                next_move = [cur+1]
            else:
                m = list(str(cur*2))
                m[0] = str(int(m[0])-1) if int(m[0])-1 > 0 else str(0)
                m = int("".join(m))
                next_move = [cur+1, m]

            for j in next_move:
                if j >= 0 and j <= 99999 and j not in visited:
                    q.append(j)
                    visited.add(j)
        step += 1

        if step > t:
            break
    return "ANG"

print(bfs(n, t, g))