백준 파이썬 7562 나이트의 이동

백준 링크:https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

최단거리를 계산하므로 BFS를 사용하면 간단히 해결 가능하다.

 

다만 배열 전부의 BFS를 구하면 많은 시간이 걸리므로 내가 원하는 배열에 도착하면 BFS를 종료시켜야한다.

from collections import deque

TC=int(input())
for i in range(TC):
    n= int(input())

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

    a,b=map(int,input().split())
    result_a,result_b=map(int,input().split())

    matrix[a][b] = 1
    queue=deque([])
    queue.append([a,b])

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

    while queue:
        x,y=queue[0][0],queue[0][1]
        if x == result_a and y == result_b:
            print(matrix[x][y]-1)
            break

        queue.popleft()

        for i in range(8):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if matrix[nx][ny] == 0:
                    queue.append([nx,ny])
                    matrix[nx][ny] = matrix[x][y] + 1