이번 문제는 BFS를 통해 해결하였다. 맨 처음에는 백트레킹을 통해 구현하였지만 시간초과가 발생하였고, BFS로 구현하였다. 중요한 포인트는 방문처리 리스트를 3차원 배열로 줘야 한다는 점이었다. 말의 움직임이 k번 남은 경우에 대한 모든 거리를 저장해주어야 답을 구할 수 있었다.

Code

import collections
k=int(input())
w, h=map(int, input().split())
grid=[list(map(int, input().split())) for _ in range(h)]
dy, dx=[0, 1, 0, -1], [1, 0, -1, 0]
hdy, hdx=[-1, 1, 2, 2, 1, -1, -2, -2], [2, 2, 1, -1, -2, -2, -1, 1]
def bfs():
    q=collections.deque()
    q.append((0, 0, k))
    visited=[[[0 for _ in range(k+1)] for _ in range(w)] for _ in range(h)]
    while q:
        y, x, horse=q.popleft()
        if (y, x)==(h-1, w-1):
            return visited[y][x][horse]
        for i in range(4):
            ny, nx=y+dy[i], x+dx[i]
            if 0<=ny<h and 0<=nx<w and grid[ny][nx]==0 and not visited[ny][nx][horse]:
                visited[ny][nx][horse]=visited[y][x][horse]+1
                q.append((ny, nx, horse))
        for i in range(8):
            ny1, nx1=y+hdy[i], x+hdx[i]
            if 0<=ny1<h and 0<=nx1<w and grid[ny1][nx1]==0 and horse>0 and not visited[ny1][nx1][horse-1]:
                visited[ny1][nx1][horse-1]=visited[y][x][horse]+1
                q.append((ny1, nx1, horse-1))
    return -1
answer=bfs()
print(answer)