백준 온라인 저지, BFS / 16948번: 데스나이트 (파이썬 / 백준 실버문제)

문제 주소: https://www.acmicpc.net/problem/16948

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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인 체스판과 두 칸 (r₁, c₁), (r₂, c₂)가 주어진다. 데스 나이트가 (r₁, c₁)에서 (r₂, c₂)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

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

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r₁, c₁, r₂, c₂가 주어진다.

출력

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

제한

예제 입력 1

7
6 6 0 1

예제 출력 1

4

예제 입력 2

6
5 1 0 5

예제 출력 2

-1

예제 입력 3

7
0 3 4 3

예제 출력 3

2

힌트

접근 방법

코드

from collections import deque
n = int(input())
r1, c1, r2, c2 = map(int, input().split())
board = [[-1 for _ in range(n)] for _ in range(n)]
queue = deque([])
queue.append([r1, c1])
board[r1][c1] = 0
while board[r2][c2] == -1 and queue:
    r, c = queue.popleft()
    for dx, dy in [[-2, -1], [-2, 1], [0, -2], [0, 2], [2, -1], [2, 1]]:
        if 0<=r+dx