(BFS) 백준 7562번 나이트의 이동

import sys
from collections import deque

input = sys.stdin.readline

T = int(input()) # 테스트 케이스 횟수 입력

for _ in range(T):
    w = int(input()) # 너비 입력

    start_x, start_y = map(int, input().split()) # 시작 좌표 입력
    end_x, end_y = map(int, input().split()) # 종료 좌표 입력

    graph = [[0 for i in range(w)] for k in range(w)] # 너비 만큼 그래프 생성 0으로 초기화

	# 나이트 이동 범위 입력
    move_x = [2, 1, 2, 1, -2, -1, -2, -1] 
    move_y = [1, 2, -1, -2, 1, 2, -1, -2]

    queue = deque() # 큐 생성
    queue.append((start_x, start_y)) # 시작 좌표 입력

    while queue:

        s1, s2 = queue.popleft() # 큐에 담겨 있는 좌표를 가져온다.

        if s1 == end_x and s2 == end_y: # 종료 조건에 맞으면 종료
            break

		# 나이트의 이동 범위만큼 모두 이동
        for i in range(8):
            nx = s1 + move_x[i]
            ny = s2 + move_y[i]

			# 범위를 벗어날 경우 종료
            if nx < 0 or ny < 0 or nx >= w or ny >= w:
                continue

			# 그래프가 0일 때 = 방문하지 않았을 경우에만 실행
            if graph[ny][nx] == 0:
                graph[ny][nx] = graph[s2][s1] + 1 # 이동된 좌표에 현재 좌표에서 1번 이동한 값인 +1을 해준다.
                queue.append((nx, ny)) # 큐에 삽입

    print(graph[end_y][end_x]) # 종료 좌표 출력