[python] 7562번 - 나이트의 이동

문제

파이썬 풀이

나이트의 이동을 좌표로 나타내면 다음과 같다.

따라서 이동 좌표들을 위와 같이 설정한 후 이동 반복문을 8번 반복하여 이동을 해준다.

그리고 이동할 때마다 이전 값에 +1한 값을 저장해준다. 그리고 목적지 좌표가 나오면 그 값에서 -1한 값을 리턴해준다(1부터 시작했으므로)

이동 좌표를 빼고는 이전 bfs들과 동일하다.

from collections import deque
import sys
input = sys.stdin.readline

t = int(input().rstrip())


def bfs() :
    dx = [-1, 1, 2, 2, 1, -1, -2, -2]
    dy = [2, 2, 1, -1, -2, -2, -1, 1]

    q = deque()
    q.append((startX, startY))
    while q :
        x, y = q.popleft()
        if x == endX and y == endY :
            return matrix[x][y] -1 
        for i in range(8) :
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<l and 0<=ny<l and matrix[nx][ny] == 0 :
                matrix[nx][ny] = matrix[x][y] + 1
                q.append((nx,ny))
                
            
        
for _ in range(t) :
    l = int(input().rstrip())
    startX, startY = map(int, input().rstrip().split())
    endX, endY = map(int, input().rstrip().split())
    matrix = [[0]*l for _ in range(l)]
    matrix[startX][startY] = 1
    print(bfs())