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():
visited = [[[[[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) for p in range(3)])
while dq:
p,y,x,n,cnt,d = dq.popleft()
if visited[d][p][y][x][n]:
continue
visited[d][p][y][x][n] = 1
if board[y][x]==n+1:
if n==N**2-1:
return cnt
dq.appendleft((p,y,x,n+1,cnt,-1))
continue
for i in [1,2]:
dq.append(((p+i)%3,y,x,n,cnt+1,-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))
else:
dq.append((p,y1,x1,n,cnt+1,i))
N = int(input())
board = [[*map(int,input().split())] for i in range(N)]
S = start()
print(BFS())0-1 BFS로 해결하였다.
풀이를 설명하면,
1. visited 배열을 8*3*N*N*N^2 크기로 만든다. visited[d][p][y][x][n]은 이전 이동방향이 d이고 현재 체스말이 p이며 n번호를 지나왔을 때 y,x를 방문했는지를 의미한다.
2. 룩과 비숍의 경우 이전 이동방향과 같은 방향으로 이동할 때 cnt를 갱신하지 않은 채 deque에 appendleft를 한다. (이전과 같은 방향으로 여러번 이동할 수 있으므로)
3. 2에 해당하지 않는 경우 cnt +1을 해주어 deque에 append한다.
4. 말을 바꾸는 경우에도 cnt +1을 해주어 append한다.
5. 찾고자 하는 번호에 도착하면 n +1을 해주고 cnt를 갱신하지 않은 채 appendleft를 한다.
6. n==N^2-1일 때, N^2에 도착하면 결과를 출력한다.
1에서 방향을 고려해준 이유는 룩과 비숍에서 방향을 고려하지 않았을 때 반례가 발생할 수 있기 때문이다.
시간복잡도는 O(N^4)이지만 N이 매우 작기 때문에 (최대 10) 여유롭게 통과 가능하다.
여담) 이 문제 숏코딩 순위 1위가 되었다.
