백준 7562 파이썬 - 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

코드

import sys
from collections import deque
t = int(sys.stdin.readline())
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]
def bfs(x1, y1, x2, y2):
    queue = deque()
    queue.append([x1, y1])
    arr[x1][y1] = 1
    while queue:
        a, b = queue.popleft()
        if a == x2 and b == y2:
            print(arr[x2][y2] - 1)
            return
        for i in range(8):
            x = a + dx[i]
            y = b + dy[i]
            if 0 <= x < n and 0 <= y < n and arr[x][y] == 0:
                queue.append([x, y])
                arr[x][y] = arr[a][b] + 1
for _ in range(t):
    n = int(sys.stdin.readline())
    x1, y1 = map(int, sys.stdin.readline().split())
    x2, y2 = map(int, sys.stdin.readline().split())
    arr = [[0] * n for _ in range(n)]
    bfs(x1, y1, x2, y2)

풀이

dx와 dy로 나이트가 움직일 수 있는 칸의 좌표를 만들어주고 움직일 수 있는 곳을 순서대로 1씩 늘려주며 입력받은 최종으로 가야하는 칸과 같아지는 경우 1을 빼서 출력한다. 이 때 맨처음 칸을 1로 만들어줬으므로 1을 뺴는 것이다.