백준 1600 말이 되고픈 원숭이 (파이썬)

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

1600번: 말이 되고픈 원숭이

1. 이동 경로를 체크하는 배열을 3차로 구성

2. 말로 이동할 수 있는 횟수를 넘지 않으면 말로 이동하는 경우와 원숭이로 이동하는 경우를 둘 다 체크

   말로 이동할 경우 세번째 차수에 1을 더해 말로 이동한 횟수를 체크하는 변수로 설정

3. 이동할 수 있는 횟수를 모두 사용한 경우 원숭이로만 이동

4. 목적지에 도착하면 이동 거리를 출력

from collections import deque
import sys

input = sys.stdin.readline

dx1 = [1, -1, 0, 0]
dy1 = [0, 0, 1, -1]
dx2 = [1, 1, -1, -1, 2, 2, -2, -2]
dy2 = [2, -2, 2, -2, 1, -1, 1, -1]

def bfs():
    q.append([0, 0, 0])
    c[0][0][0] = 1
    while q:
        x, y, z = q.popleft()
        if x == h-1 and y == w-1:
            print(c[x][y][z]-1)
            return
        if z < k:
            horse(x, y, z)
            monkey(x, y, z)
        elif z == k:
            monkey(x, y, z)

    print(-1)

def horse(x, y, z):
    for i in range(8):
        nx = x + dx2[i]
        ny = y + dy2[i]
        if 0 <= nx < h and 0 <= ny < w:
            if a[nx][ny] == 0 and c[nx][ny][z+1] == 0:
                c[nx][ny][z+1] = c[x][y][z] + 1
                q.append([nx, ny, z+1])

def monkey(x, y, z):
    for i in range(4):
        nx = x + dx1[i]
        ny = y + dy1[i]
        if 0 <= nx < h and 0 <= ny < w:
            if a[nx][ny] == 0 and c[nx][ny][z] == 0:
                c[nx][ny][z] = c[x][y][z] + 1
                q.append([nx, ny, z])

k = int(input())
w, h = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
c = [[[0]*(k+1) for _ in range(w)] for _ in range(h)]
q = deque()

bfs()