이번 문제는 BFS를 통해 해결하였다. BFS 안에서 나이트의 이동을 구현하기 위해 나이트의 이동 정보를 리스트에 짝지어 담아 모든 경우를 순회하도록 하였다. 그리고 BFS 안에서 목적지에 도달하면 현재까지의 누적 이동 횟수를 출력하고 반복문을 탈출하도록 하였다.

• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> l을 입력받는다.
  -> f_y, f_x를 입력받는다. (출발점)
  -> t_y, t_x를 입력받는다. (도착점)
  -> 나이트 이동의 8가지 방향을 짝지어 dy, dx 리스트에 저장한다.
  -> 방문처리 리스트 visited를 False l*l만큼 저장한다.
  -> visited[f_y][f_x]를 True로 갱신한다.
  -> BFS에 사용할 큐 q를 데크로 선언한다.
  -> q에 (0, f_y, f_x)를 넣는다.
  -> q가 존재할동안 반복하는 while문을 돌린다.
  --> cnt, y, x를 q에서 추출한다.
  --> 만약 y가 f_y와 같고, x가 f_x와 같을 경우,
  ---> cnt를 출력하고, 종료한다.
  --> 8번 반복하는 i에 대한 for문을 돌린다.
  ---> ny에 y+dy[i]를 저장한다.
  ---> nx에 x+dx[i]를 저장한다.
  ---> nxt_cnt에 cnt+1을 저장한다.
  ---> 만약 ny와 nx가 0보다 크거나 같고 l보다 작고, visited[ny][nx]가 False일 경우,
  ----> visited[ny][nx]를 True로 갱신하고 q에 (nxt_cnt, ny, nx)를 넣는다.

Code

import collections
t=int(input())
for _ in range(t):
    l=int(input())
    f_y, f_x=map(int, input().split())
    t_y, t_x=map(int, input().split())
    dy=[2, 2, -2, -2, 1, 1, -1, -1]
    dx=[-1, 1, 1, -1, 2, -2, 2, -2]
    visited=[[False]*l for _ in range(l)]
    visited[f_y][f_x]=True
    q=collections.deque()
    q.append((0, f_y, f_x))
    while q:
        cnt, y, x=q.popleft()
        if y==t_y and x==t_x:
            print(cnt)
            break
        for i in range(8):
            ny=y+dy[i]
            nx=x+dx[i]
            nxt_cnt=cnt+1
            if 0<=ny<l and 0<=nx<l and not visited[ny][nx]:
                visited[ny][nx]=True
                q.append((nxt_cnt, ny, nx))