[백준] 17391번 무한부스터 파이썬

문제

카트라이더를 처음 시작하는 카린이 정범이는 어려운 조작법에 실망감이 커져가고 있다. 드리프트, 순간 부스터, 커팅, 톡톡이 등등 어려운 테크닉에 질린 정범이는 그나마 쉬운 ‘숭고한 무한부스터 모드’에 도전해보려고 한다.

‘숭고한 무한부스터 모드’는 크기 N × M 의 직사각형 모양의 맵에서 진행되며, 맵 전체가 단위 격자로 구성되어 있다. 기존의 ‘무한부스터 모드’와는 다르게, 모든 격자 안에는 특정 개수의 부스터 아이템이 위치한다. 이 모드에서 플레이의 방식은 다음과 같다.

처음에 플레이어의 카트바디는 출발지점인 1행 1열에 위치하며, 멈춰 있는 상태이고, 보유하고 있는 부스터 아이템의 개수는 0개이다. 목표는 도착지점인 N행 M열의 격자에 도달하는 것이며, 도달하는 즉시 게임이 종료된다. 카트바디가 격자에 멈추어 있을 때, 격자에 놓여있는 부스터 아이템을 자동으로 전부 습득하게 된다. 이 과정에서 x개를 습득했다면 한 방향을 정해 오른쪽으로 최대 x칸을 가거나, 아래쪽으로 최대 x칸을 이동할 수 있으며, 1칸 단위로 이동하게 된다. 예를 들어 부스터 아이템을 3개 습득했을 때, 오른쪽으로 2칸 이동이나 아래쪽으로 3칸 이동은 가능하지만, 오른쪽으로 1칸 이동 후 아래로 2칸 이동이나 왼쪽으로 1칸 이동이나 아래쪽으로 2.718칸 이동은 불가능하다. 이동 후 멈추면서 보유하고 있던 부스터 아이템은 모두 소진된다.

이동중에 멈추지 않고 지나치는 격자의 부스터 아이템은 습득할 수 없으며, 카트바디는 맵을 벗어나는 방향으로는 움직일 수 없다.

정범이는 ‘숭고한 무한부스터 모드’에서 출발지점부터 도착지점까지 주행하면서 부스터 아이템을 획득하게 되는 격자의 개수를 최소화하고 싶다. 카린이 정범이를 도와주도록 하자.

입력

첫 번째 줄에 맵의 세로 길이와 가로 길이를 나타내는 양의 정수 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 300)

두 번째 줄부터 N개의 줄에 걸쳐 각 격자에 있는 부스터 아이템 개수인 M개의 양의 정수 aij*가 공백으로 구분되어 주어진다. (1 ≤ *aij ≤ max(N, M)) aij*는 *i 행 j 열의 격자에 있는 부스터 아이템 개수이다.

출발지점과 도착지점은 다르다.

출력

첫 번째 줄에 정범이가 맵의 출발지점부터 도착지점까지 이동하면서 부스터 아이템을 획득하게 되는 격자의 최소 개수를 출력한다.

예제 입력 1

4 5
1 1 4 1 3
3 4 1 3 2
1 1 5 3 2
5 3 1 1 1

예제 출력 1

3

제출 답안

from collections import deque
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**5)

dy = [0, 1]
dx = [1, 0]

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
direction = [[0, 1], [1, 0]]
visited = [[0] * m for _ in range(n)]
visited[0][0] = 0
q = deque([(0, 0)])

while q:
    y, x = q.popleft()
    for i in range(2):
        ny, nx = y, x
        for j in range(board[y][x]):
            ny, nx = ny + dy[i], nx + dx[i]
            if 0 <= ny < n and 0 <= nx < m and visited[ny][nx] == 0:
                q.append((ny, nx))
                visited[ny][nx] = visited[y][x] + 1

print(visited[-1][-1])