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

 
 
# temp 리스트를 추가해서 count를 계산하려고 했지만 시간 초과가 났다.
# 구글링을 해보니 2차원 리스트를 통한 풀이가 있어 이를 참고했다. 풀 수 있던 문제였는데 아깝네요
 
 
import sys
from collections import deque
 
def bfs(a,b,x,y,length):
 
    # 시작 위치 a,b
 
    # 도착 위치 x,y
 
    count = 0
 
    queue = deque()
 
    queue.append([a,b])
 
    dx = [2,2,1,1,-1,-1,-2,-2]
    dy = [1,-1,2,-2,2,-2,1,-1]
 
    temp = [ ]
 
 
    while queue:       
 
        n,m = queue.popleft()
 
        if n==x and m==y:
            return answer[n][m]-1
 
 
        for i in range(8):
            temp_x = n + dx[i]
            temp_y = m + dy[i]
 
            if 0<=temp_x<length and 0<=temp_y<length and answer[temp_x][temp_y]==0:
 
                answer[temp_x][temp_y] = answer[n][m] + 1
                queue.append([temp_x,temp_y])
 
 
 
 
 
 
 
 
num = int(sys.stdin.readline())
 
for i in range(num):
 
    length = int(sys.stdin.readline())
 
    a,b = list(map(int,sys.stdin.readline().split(" ")))
 
    x,y = list(map(int,sys.stdin.readline().split(" ")))
 
    answer = [[0]*(length+1) for i in range(length+1)]
 
    answer[a][b] = 1
 
    print(bfs(a,b,x,y,length))