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위가 되었다.