[백준 16952번] 체스판 여행 2 (Python3)

from collections import *
dy = [[1,-1,0,0],[1,-1,1,-1],[1,1,-1,-1,2,2,-2,-2]]
dx = [[0,0,1,-1],[1,1,-1,-1],[2,-2,2,-2,1,-1,1,-1]]

def start():
  for i in range(N):
    for j in range(N):
      if board[i][j]==1:
        return i,j

def BFS():
  result = C = 1e5
  visited = [[[[[(1e5,0)]*N*N for i in range(N)] for i in range(N)] for i in range(3)] for i in range(8)]
  dq = deque([(p,*S,1,0,-1,0) for p in range(3)])
  while dq:
    p,y,x,n,cnt,d,c = dq.popleft()
    cnt1,c1 = visited[d][p][y][x][n]
    if cnt1<cnt or cnt1==cnt and c1<=c:
      continue
    visited[d][p][y][x][n] = (cnt,c)
    if board[y][x]==n+1:
      if n==N**2-1:
        if result < cnt:
          return result,C
        else:
          result,C = cnt,min(C,c)
          continue
      dq.appendleft((p,y,x,n+1,cnt,-1,c))
      continue
    for i in [1,2]:
      dq.append(((p+i)%3,y,x,n,cnt+1,-1,c+1))
    for i in range(len(dy[p])):
      y1,x1 = y+dy[p][i],x+dx[p][i]
      if N>y1>=0 and N>x1>=0:
        if p!=2 and i==d:
          dq.appendleft((p,y1,x1,n,cnt,i,c))
        else:
          dq.append((p,y1,x1,n,cnt+1,i,c))

N = int(input())
board = [[*map(int,input().split())] for i in range(N)]
S = start()
print(*BFS())

체스판 여행 [백준 16959번] 체스판 여행 1 (Python3) (tistory.com) 을 약간만 변형시키면 된다.

visited에 0 또는 1로 체크하는 것이 아니고 튜플 (cnt,c)로 체크한다. cnt는 이동횟수를, c는 기물변경횟수를 의미한다.

그리고 이동횟수가 갱신되거나, 이동횟수는 같은데 기물변경횟수가 갱신되는 경우에만 BFS를 실행하면 된다.

 

여담) 이 문제도 숏코딩 순위 1위가 되었다.