백준 7562번 나이트의 이동

bfs문제로 이동하는 경우의 수가 8개이고 2차원(좌표)을 이용하기 때문에 딕셔너리는 사용하지 못한다(딕셔너리의 key값에는 리스트가 들어갈 수 없다) 다라서 2차원 리스트로 이동경로를 저장해야한다

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

dx=[-1,1,-2,2,-1,1,-2,2] #이동하는 경우의수 8가지
dy=[2,2,1,1,-2,-2,-1,-1]

case = int(input())

for i in range(case):
    line = int(input())
    nx,ny = map(int,input().split())
    ex,ey = map(int,input().split())

    q = deque()
    q.append([nx,ny])

    list1= [[0 for _ in range(line)] for _ in range(line)] #2차원 배열 만들기


    while q:#큐를 실행

        x,y = q.popleft()
        
        if x == ex and y == ey:#조건을 만족할시 탈출
            print(list1[x][y])
            break
        
        for i in range(8):
            a = x +dx[i]
            b = y +dy[i]

            if a<0 or b<0 or a>=line or b>=line:
                continue

            if list1[a][b] == 0: #중복을 방지한다
                list1[a][b] = list1[x][y]+1
                q.append([a,b])