백준 1600번 말이 되고픈 원숭이 (Python 3)

Baekjoon online judge 1600번 파이썬

 

링크

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

1600번: 말이 되고픈 원숭이

벽 부수고 이동하기2 와 같은 아이디어

visited를 2차원이 아닌 3차원으로 관리한다 (말로 이동 한 수 + x + y)

3차원으로 관리하는 이유는, 먼저 방문했다고 해서 그 경우가 최적이 아닐수 있기 때문이다. (가장 적은 횟수로 먼저 접근 가능한건 맞지만, 말로 이동한 횟수까지 최적이라고 할 수 없다.) 더 오래 걸리더라도 결과적으로는 최적일 수 있다.

소스코드

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

def bfs(sx,sy,sk):
  queue=deque()
  visited=[[[-1 for _ in range(w)] for _ in range(h)] for _ in range(sk+1)]
  visited[0][sy][sx]=0
  queue.append([sx,sy,0])
  #x,y,k
  knight=[[2,1],[-2,1],[2,-1],[-2,-1],[1,2],[-1,2],[1,-2],[-1,-2]]
  index=[[1,0],[-1,0],[0,1],[0,-1]]
  while queue:
    x,y,k=queue.popleft()
    if x==w-1 and y==h-1:
      return visited[k][y][x]
    if k<sk:
      for indx,indy in knight:
        ny=y+indy
        nx=x+indx
        if 0<=nx<w and 0<=ny<h and visited[k+1][ny][nx]==-1 and map_data[ny][nx]!=1:
          visited[k+1][ny][nx]=visited[k][y][x]+1
          queue.append([nx,ny,k+1])

    for indx,indy in index:
      ny=y+indy
      nx=x+indx
      if 0<=nx<w and 0<=ny<h and visited[k][ny][nx]==-1 and map_data[ny][nx]!=1:
        visited[k][ny][nx]=visited[k][y][x]+1
        queue.append([nx,ny,k])
  return -1


k=int(input())
w,h=map(int,input().split())
map_data=[list(map(int,input().split())) for _ in range(h)]
print(bfs(0,0,k))