[백준][BFS] 7562.나이트의 이동 (파이썬/Python)

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

def bfs(sx,sy,ex,ey):
    q = deque()
    q.append([sx,sy])
    dist[sx][sy] = 1
    while q:
        x,y = q.popleft()
        if x == ex and y == ey:
            print(dist[ex][ey]-1)
            return
        for i in range(8):
            nx = dx[i] + x
            ny = dy[i] + y
            if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == 0:
                q.append([nx,ny])
                dist[nx][ny] = dist[x][y] + 1
    


t = int(input())
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]


for _ in range(t):
    n = int(input())
    dist = [[0]*n for _ in range(n+1)]
    sx, sy = map(int,input().split())
    ex, ey = map(int,input().split())
    bfs(sx,sy,ex,ey)

# 일직선상으로 이동이 불가하고 현재 범위에서 한 칸은 다 띄워두고 가야 하는 문제로 범위만 제대로 설정하면 bfs를 사용해서 어렵지 않게 풀 수 있는 문제.

# 이동 횟수와 관련된 문제로 BFS를 사용해 풀어야 한다.(최단거리를 구하는 문제이기 때문 -> 가중치가 있다면 다익스트라 사용 그러나 지금은 가중치가 없기에 BFS로도 충분히 풀이 가능)