데스나이트

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

해결방안

• 최소 이동횟수를 구해야하기 때문에 bfs를 이용한다.
• 이동 반경을 설정하고 bfs를 돌린다.

from collections import deque 
N = int(input())
sr,sc,er,ec = map(int,input().split())

#체스판과 방문표시 만들기 
grid = [[0]*N for _ in range(N)]
visited= [[0]*N for _ in range(N)]

#큐에 시작점 넣기 
q = deque([[sr,sc]])
visited[sr][sc] = 1 

#이동 반경 
dr = [-2,-2,0,0,2,2]
dc = [-1,1,-2,2,-1,1]

#bfs 돌리기 
while q :
    r,c = q.popleft()
    if r == er and c == ec :
        break 
    for d in range(6) :
        nr = r+ dr[d]
        nc = c + dc[d]
        if 0<=nr<N and 0<=nc<N and not visited[nr][nc] :
            q.append([nr,nc])
            grid[nr][nc] = grid[r][c]+1 
            visited[nr][nc] = 1 

if grid[er][ec] :
    ans = grid[er][ec]
else :
    ans = -1 
print(ans)