[백준] 7562번 나이트의 이동 [Python]

• 문제 : https://www.acmicpc.net/problem/7562

• BFS

n = int(input())

for i in range(n):
    l = int(input()) # 체스판 크기 ㅣ * ㅣ
    now = list(map(int, input().split()))    # 현재 위치
    target = list(map(int, input().split()))    # 목표 위치

    visit = [[0] * l for _ in range(l)]
    zx, zy = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, -2, -1, 1, 2]
    Q = [now]
    visit[now[0]][now[1]] = 1

    while Q:
        x, y = Q.pop(0)

        if x == target[0] and y == target[1]:
            print(visit[x][y] - 1)
            break

        for i in range(8):
            nx, ny = x + zx[i], y + zy[i]

            if 0 <= nx < l and 0 <= ny < l and visit[nx][ny] == 0:
                visit[nx][ny] = visit[x][y] + 1
                Q.append([nx, ny])