백준. 7526번. 나이트의 이동 파이썬 풀이

백준. 7526번. 나이트의 이동 파이썬 풀이

문제링크 https://www.acmicpc.net/problem/7562

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10**6)

from collections import deque



# 나이트 이동 경우
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]


def bfs(x_1, y_1, tx, ty):
    queue = deque()
    queue.append([x_1, y_1])
    graph[x_1][y_1] = 1

    while queue:
        now_x, now_y = queue.popleft()
        if now_y == ty and now_x == tx:
            print(graph[tx][ty]-1)
            return
        for i in range(8):
            nx = now_x + dx[i]
            ny = now_y + dy[i]
            if 0 <= ny < n and 0 <= nx < n and graph[nx][ny] == 0:
                graph[nx][ny] = graph[now_x][now_y] + 1
                queue.append([nx, ny])


# 테스트케이스 개수 t
t = int(input())

# 테스트케이스만큼 반복
for i in range(t):
    # 체스판 한 변의 길이 n
    n = int(input())
    # 현재 나이트의 위치
    x, y = map(int, input().split())
    # 이동하려고 하는 칸
    target_x, target_y = map(int, input().split())

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

    bfs(x, y, target_x, target_y)