[백준] [Python] 7562번 나이트의 이동 - BFS

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

Python

import sys
from collections import deque

dx = [1,1,-1,-1,2,2,-2,-2]
dy = [2,-2,2,-2,1,-1,1,-1]

for _ in range(int(sys.stdin.readline().rstrip())):
    l = int(sys.stdin.readline().rstrip())
    board = [[0]*l for _ in range(l)]
    now = list(map(int,sys.stdin.readline().split()))
    dest = list(map(int,sys.stdin.readline().split()))

    q = deque()
    q.append(now)
    
    while q:
        pos = q.popleft()
        
        if board[pos[0]][pos[1]] == 0:
            board[pos[0]][pos[1]] = 1
            
        for i in range(8):
            nx = pos[0]+dx[i]
            ny = pos[1]+dy[i]
            if 0<=nx<l and 0<=ny<l:
                if board[nx][ny]==0:
                    q.append([nx,ny])
                    board[nx][ny] = board[pos[0]][pos[1]]+1

    print(board[dest[0]][dest[1]]-1)