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

아주 쉬운 문제다.

전형적인 삼차원 배열을 이용하여 bfs 탐색을 푸는 문제

k번까지 말처럼 이동할 수 있으니

dist=[[[-1]*w for _ in range(h)] for _ in range(k+1)]으로 선언하여

말처럼 이동하면 dist[k+1][nx][ny]=dist[k][x][y]+1,원숭이처럼 이동하면 dist[k][nx][ny]=dist[k][x][y]+1 로 해주면 된다.

 

import sys
from collections import deque
from itertools import combinations
 
 
if __name__=='__main__':
   # sys.stdin=open("input.txt", "rt")
    
    k=int(input()) ##원숭이처럼 이동할 수 있는 제한 횟수
    w,h=map(int,input().split()) ## w=가로 길이(열), h=세로 길이(행)
 
    board=[list(map(int,input().split())) for _ in range(h)]
    dist=[[[-1]*w for _ in range(h)] for _ in range(k+1)]
 
 
    q=deque()
 
    q.append((0,0,0)) ##출발점 (원숭이,x좌표,y좌표)
    dist[0][0][0]=0
    dx=[0,0,-1,1,-1,-2,-2,-1,1,2,2,1]
    dy=[1,-1,0,0,-2,-1,1,2,-2,-1,1,2]
 
    while q:
 
        mk,x,y=q.popleft()
 
        for i in range(12):
            nx=x+dx[i]
            ny=y+dy[i]
 
            if 0<=nx<h and 0<=ny<w:
                if board[nx][ny]==0:
                        if i<4:
                          if dist[mk][nx][ny]==-1:
                              dist[mk][nx][ny]=dist[mk][x][y]+1
                              q.append((mk,nx,ny))
                        else:
                            if mk+1<=k and dist[mk+1][nx][ny]==-1:
                                dist[mk+1][nx][ny]=dist[mk][x][y]+1
                                q.append((mk+1,nx,ny))
 
    res=float('inf')
    for i in range(k+1):
        if dist[i][h-1][w-1]!=-1:
            res=min(res,dist[i][h-1][w-1]) 
 
    if res==float('inf'):
        print(-1)
    else:
        print(res)