백준 | 나이트의 이동

백준 나이트의 이동

import sys
from collections import deque

# commands: 나이트가 이동할 수 있는 8가지 방향
commands = [(1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1), (-2, 1), (-1, 2)]

def bfs(l, start, end):
    visited = [[False] * l for _ in range(l)]
    visited[start[0]][start[1]] = True

    queue = deque([(start[0], start[1], 0)])
    while queue:
        x, y, cnt = queue.popleft()

        if (x, y) == end:
            return cnt

        for command in commands:
            nx = x + command[0]
            ny = y + command[1]

            if 0 <= nx < l and 0 <= ny < l:
                if not visited[nx][ny]:
                    queue.append((nx, ny, cnt + 1))
                    visited[nx][ny] = True
    
    return -1

t = int(sys.stdin.readline())
for _ in range(t):
    l = int(sys.stdin.readline())
    start = tuple(map(int, sys.stdin.readline().split()))
    end = tuple(map(int, sys.stdin.readline().split()))

    print(bfs(l, start, end))