BOJ - 17391 - 무한부스터

import sys
from collections import deque

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

def BFS(maps, N, M):
    dq = deque()
    dq.append((0, 0, 0))

    check = [[False for _ in range(M)] for _ in range(N)]
    check[0][0] = True

    while dq:
        x, y, w = dq.popleft()
        if x == N-1 and y == M-1:
            return w

        for i in range(2):
            for j in range(1, maps[x][y]+1):
                nx = x + dx[i] * j
                ny = y + dy[i] * j
                if 0 <= nx < N and 0 <= ny < M:
                    if not check[nx][ny]:
                        dq.append((nx, ny, w + 1))
                        check[nx][ny] = True

def solution():
    N, M = map(int, sys.stdin.readline().split())
    maps = []
    for _ in range(N):
        maps.append(list(map(int, sys.stdin.readline().split())))

    print(BFS(maps, N, M))

solution()

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