[백준] 7562: 나이트의 이동 (Python)

문제📖

풀이🙏

• 먼저 나이트가 움직일 수 있는 범위를 dx, dy에 저장한다.
• bfs를 이용하여 나이트가 이동할 수 있는 범위일 경우 그 값을 초기화하면서 도달하고자 하는 좌표에 도착하면 그 값을 출력한다.

코드💻

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, y, target_x, target_y):
    queue = deque()
    queue.append([x,y])
    graph[x][y] = 1
    while queue:
        a, b = queue.popleft()
        if a == target_x and b == target_y:
        	# 시작이 1 이였으므로 1을 빼준다.
            print(graph[a][b]-1)
            return
        for i in range(8):
            nx = a+dx[i]
            ny = b+dy[i]

            if 0<=nx<n and 0<=ny<n and graph[nx][ny]==0:
                graph[nx][ny] = graph[a][b]+1
                queue.append([nx, ny])                

for _ in range(int(input())):
    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)