본문 바로가기

카테고리 없음

[백준 16959번] 체스판 여행 1 (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():
  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위가 되었다.