문제

입력 , 출력

풀이

import sys
from collections import deque
sys.setrecursionlimit(100000)  # 재귀 최대깊이를 정해줌


def dfs(x1, y1, x2, y2):
    dq = deque()
    dq.append([x1, y1])
    arr[x1][y1] = 1
    while dq:
        x, y = dq.popleft()
        if x == x2 and y == y2:
            return arr[x][y]-1
        for i in range(8):
            nx = dx[i] + x
            ny = dy[i] + y
            if(nx >= 0 and nx < a and ny >= 0 and ny < a):
                if arr[nx][ny] == 0:
                    dq.append([nx, ny])
                    arr[nx][ny] = arr[x][y] + 1


n = int(input())

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

for i in range(n):
    a = int(input())
    arr = [[0 for _ in range(a)] for _ in range(a)]
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    print(dfs(x1, y1, x2, y2))

설명

dx , dy 나이트가 이동할수 있는 모든 경우의 수 총 8가지
반복문을 사용해서 그래프 범위내에서 갈수 있는 모든경우의 수를 확인함
타겟 목표에 도착하면 나이트의 이동횟수를 return하여 출력함

실수한 부분

dq를 pop할때 선입선출을 하니 방문했던 노드 확인 조건을 0으로 해놔서
답이 매우 커졌음
fifo를 사용할지 lifo를 사용할지 잘 봐야할것같음..