[백준_7562] 나이트의 이동 python

최소 경로를 탐색해야 하는 문제이므로,

dfs가 아닌 bfs를 사용해야 한다.

경로는 step배열을 이용하여 구한다.

# 큐 사용 위한 준비
from collections import deque

# t 입력
t = int(input())

# n 입력
for _ in range(t):
    n = int(input())

    # 시작 위치 입력
    s_x, s_y = map(int, input().split())
    # 종료 위치 입력
    e_x, e_y = map(int, input().split())

    # grid
    grid = [
        [0] * n
        for _ in range(n)
    ]

    # visited
    visited = [
        [0] * n
        for _ in range(n)
    ]

    # step
    step = [
        [0] * n
        for _ in range(n)
    ]

    # in_range(x, y)
    def in_range(x, y):
        return 0 <= x and x < n and 0 <= y and y < n

    # check(x, y)
    def check(x, y):
        # 격자 내에 있고, 방문한 적 없어야 함
        return in_range(x, y) and not visited[x][y]

    # bfs()
    def bfs():
        # 큐 안에 원소가 없어질 때까지 반복
        while q:
            
            # 언팩킹
            x, y = q.popleft()

            # dxs, dys
            dxs, dys = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, 2, 1, -1, -2]
            for dx, dy in zip(dxs, dys):
                # 다음 조사 위치
                nx, ny = x + dx, y + dy
                # 다음 위치로 이동이 가능하면
                if check(nx, ny):
                    # 방문 처리 해주고
                    visited[nx][ny] = 1
                    # 큐에 넣어주고
                    q.append((nx, ny))
                    # step에 시간 기록
                    step[nx][ny] = step[x][y] + 1

    
    # 설계
    
    # 큐
    q = deque()
    
    # 방문 표시 해주고
    visited[s_x][s_y] = 1
    
    # 큐에 넣어주고
    q.append((s_x, s_y))

    # bfs 돌려주기
    bfs()

    # 출력
    print(step[e_x][e_y])