[Baekjoon] 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인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

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

입력

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

출력

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

예제

Example 1:

Input: 
7
6 6 0 1
Output: 
4

Example 2:

Input:
6
5 1 0 5
Output:
-1

Example 3:

Input:
7
0 3 4 3
Output:
2

조건

시간 제한 : 2초

메모리 제한 : 512 MB

풀이과정

풀이

from collections import deque

n = int(input())

r1, c1, r2, c2 = map(int, input().split())

q = deque()

q.append((r1, c1, 0))

visit = [[False]*n for _ in range(n)]
visit[r1][c1] = True

dx = [-2,-2,0,0,2,2]
dy = [-1,1,-2,2,-1,1]

move = False
while q:
    r, c, cnt = q.popleft()
    if r == r2 and c == c2:
        move = True
        print(cnt)
        break
    for i in range(6):
        nr = r + dx[i]
        nc = c + dy[i]
        if nr < 0 or nc < 0 or nr >= n or nc >= n:
            continue
        if visit[nr][nc] == False:
            visit[nr][nc] = True
            q.append((nr,nc,cnt+1))

if move == False:
    print(-1)