[Algorithm] BaekJoon : 1600. 馬になりたい猿bypython

[問題のショートカット]https://www.acmicpc.net/problem/1600

📌問題の説明

動物園から逃げ出したばかりのサルが世界を一周している.あいつは馬になりたくない.だから彼は馬の動きを注意深く観察して、そのとおりにすることにした.話が戻る.馬は格子板にチェスのナイトのような移動方式があります.次の図は馬の移動方法を示しています.馬がxマークのところに行けるという意味です.ちなみに馬は障害物を飛び越えることができます.

しかしサルには錯覚があった.馬はそのように動くことができますが、サルは能力が足りず、全部でK回以上しか移動できません.それ以外は隣の格子に移動するしかありません.対角線方向は隣接するセルには含まれません.
今サルは遠い旅に出る.グリルプレートの一番左上から、一番右下まで.隣接する4つの方向が1回移動し、馬の1回の移動は、いずれも1回の動作となります.指定したグリッドでサルが始点から終点まで最小限の動作をする方法を理解するプログラムを作成します.
入力
最初の行は整数Kを与える.2行目は、メッシュプレートの横方向長さW、縦方向長さHを与える.そしてH行にW個の数字があり、0は何もない平地を表し、1は障害物を表す.障害物のある場所に移動することはできません.始点と終点はいつも平らだ.WとHは1以上200以下の自然数、Kは0以上30以下の整数である.
しゅつりょく
1行目はサルの動作数の最高値を出力します.始点から終点まで出力できない場合は、-1を出力します.

💡 問題を解く

BFSを用いて(0,0)~(H−1,W−1)サルの動作数の最小値を求める問題である.
このとき,サルはチェスのナイトのようにKを移動することができる.
それ以外は4方向(上、下、左、右)しか移動できません.
「馬」の移動は「四方向」よりも遠くに移動できます.
所与のグリッド(地図)に「壁」が存在するため、「馬」の移動に移動できない場合もあれば、(H−1,W−1)座標に正確に到達できない場合もある.
つまり、Kを多く使うことは答えを意味しない.
最適Kが到達点の最小移動数を用いることを知るために,アクセスを3次元に並べた.
→1+1(使用しない場合は含む)の1次元配列を行(H)x列(W)次元に設定します.
アクセス時に、移動する座標(r,c)にk個の数を使用する最小動作数を入力します.

「馬」移動時:アクセス済み[nr][nc][k+1]=アクセス済み[r][c][k]+1

「馬」未移動:アクセス[nr][nc][k]=アクセス[r][c][k]+1

コードは次のとおりです.

import sys
from collections import deque

d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
hd = [(-1, -2), (-2, -1), (-2, 1), (-1, 2),
      (1, -2), (2, -1), (2, 1), (1, 2)]

def check(nr, nc, k): # 이동 가능 여부 확인
    if 0 <= nr < H and 0 <= nc < W and not visited[nr][nc][k] and maps[nr][nc] == 0:
        return True
    return False

def bfs():
    queue = deque([(0, 0, 0)])
    while queue:
        r, c, k = queue.popleft()
        if r == H-1 and c == W-1: # 도착점인 경우
            return visited[r][c][k]-1 # 동작수의 최소값 return
        for idx in range(4): # 4방향으로 이동하는 경우
            nr = r + d[idx][0]
            nc = c + d[idx][1]
            if check(nr, nc, k):
                queue.append((nr, nc, k))
                visited[nr][nc][k] = visited[r][c][k] + 1
        if k < K: # '말'의 움직임으로 이동하는 경우(k사용)
            for idx in range(8):
                nr = r + hd[idx][0]
                nc = c + hd[idx][1]
                if check(nr, nc, k+1):
                    queue.append((nr, nc, k+1))
                    visited[nr][nc][k+1] = visited[r][c][k] + 1
    return -1 # 도착점으로 이동하지 못할 경우 -1 return

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

visited = [[[0] * (K + 1) for _ in range(W)] for _ in range(H)]
visited[0][0][0] = 1

print(bfs())