BOJ - 1600 - 말이 되고픈 원숭이

import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
kx = [-2, -1, 1, 2, 2, 1, -1, -2]
ky = [1, 2, 2, 1, -1, -2, -2, -1]

def BFS(arr, K, W, H):
    dq = deque()
    visit = [[[0 for _ in range(31)] for _ in range(W)] for _ in range(H)]
    dq.append((0, 0, K))

    while dq:
        x, y, w = dq.popleft()
        if x == H - 1 and y == W - 1: return visit[x][y][w]

        if w > 0:
            for k in range(8):
                nx = x + kx[k]
                ny = y + ky[k]

                if 0 <= nx < H and 0 <= ny < W:
                    if arr[nx][ny] == 0:
                        if visit[nx][ny][w - 1] == 0:
                            dq.append((nx, ny, w - 1))
                            visit[nx][ny][w - 1] = visit[x][y][w] + 1
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < H and 0 <= ny < W:
                if arr[nx][ny] == 0:
                    if visit[nx][ny][w] == 0:
                        dq.append((nx, ny, w))
                        visit[nx][ny][w] = visit[x][y][w] + 1

    return -1

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

    print(BFS(maps, K, W, H))

solution()

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