230. 말이 되고픈 원숭이

백준

1. BFS

참고

import sys
from collections import deque
input = sys.stdin.readline

k = int(input())
m, n = map(int, input().split())
table = [list(map(int, input().split())) for _ in range(n)]

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

hx = [-1, -2, -1, -2, 1, 2, 1, 2]
hy = [-2, -1, 2, 1, -2, -1, 2, 1]

#총 K개의 특수 이동을 고려해야 하므로 3차원 검사 배열
check = [[[False] * (k + 1) for _ in range(m)] for _ in range(n)]

def go(a, b):
  q = deque()
  q.append((a, b, 0, 0))
  check[a][b][0] = True
  while q:
    x, y, skill, count = q.popleft()
    if x == n - 1 and y == m-1:
      return count
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m:
        if check[nx][ny][skill] == False:
          if table[nx][ny] == 0:
            check[nx][ny][skill] = True
            q.append((nx, ny, skill, count + 1))
            
    #특수이동이 가능한 경우
    if skill < k:
      for i in range(8):
        nx = x + hx[i]
        ny = y + hy[i]
        if 0 <= nx < n and 0 <= ny < m:
          if check[nx][ny][skill + 1] == False:
            if table[nx][ny] == 0:
              check[nx][ny][skill + 1] = True
              q.append((nx,ny,skill + 1, count + 1))
  return -1

print(go(0,0))