문제출처 : https://www.acmicpc.net/problem/7562

풀이과정

1. 나이트가 움직일 수 있는 direction을 모두 고려한다.

2. bfs를 진행하며 나이트를 이동시킨다.

import sys
from collections import deque
input = sys.stdin.readline


def bfs(x,y,tx,ty):
    dx=[-2,-2,1,1,-1,-1,2,2]
    dy=[-1,1,2,-2,-2,2,1,-1]
    q = deque()
    q.append([x,y])
    check[x][y] = 1

    while q:
        a,b = q.popleft()
        for i in range(len(dx)):
            if 0<=a+dx[i]<length and 0<=b+dy[i]<length and check[a+dx[i]][b+dy[i]] == 0:
                check[a+dx[i]][b+dy[i]] = check[a][b] + 1
                q.append([a+dx[i],b+dy[i]])
            
            if a == tx and b == ty:
                return check[tx][ty] - 1


n = int(input())

for i in range(n):
    length = int(input())
    check = [[0]*length for j in range(length)]
    x, y = list(map(int,input().split()))
    tx, ty = list(map(int,input().split()))
    print(bfs(x,y,tx,ty))