백준 알고리즘 7562번 나이트의 이동(python)

최단경로를 찾아야 되는 기본적인 BFS 문제이다.

bfs 함수에서 반복문 4번(위, 아래, 오른쪽, 왼쪽) 돌아가던걸 나이트의 이동경로에 맞게 8번 돌도록 바꿔주면 끝이다.

from collections import deque

def bfs(y, x):
    queue = deque()
    queue.append((y, x))
    d = [(2, -1), (2, 1), (-2, -1), (-2, 1), (1, -2), (1, 2), (-1, -2), (-1, 2)]
    while queue:
        y, x = queue.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < l) and (0 <= X < l) and graph[Y][X] == 0:
                queue.append((Y, X))
                graph[Y][X] = graph[y][x] + 1
                if y == ey and x == ex:
                    return ;
        
for _ in range(int(input())):
    l = int(input())
    sy, sx = map(int, input().split())
    ey, ex = map(int, input().split())
    graph = [[0]*l for _ in range(l)]
    bfs(sy, sx)
    print(graph[ey][ex])