그냥 한번에 맞춰버려서 깜짝 놀라버림..
사실 지금까지 테스트케이스 돌리면서
에러가 안 뜬 적이 한번도 없는데
테스트 케이스가 한번에 깔끔하게 나와서 어? 해버림..
📍우선 BFS로 풀어야 되겠다고 생각했다. DFS는 잘못된 루트를 선택하는 순간 시간이 오래걸릴 것 같다는 생각이 듦.
📍나이트를 이동시켜주며 조건에 맞다면 deque에 넣고 횟수를 graph에 저장했다! 조건에 맞다면 break로 루프를 바로 빠져나오도록 함!
import sys
from collections import deque
n = int(input())
def bfs(graph, queue, goal, size):
move = [(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2)]
while queue:
x, y = queue.popleft()
if x == goal[0] and y == goal[1]:
break
for i in range(8):
nx = x + move[i][0]
ny = y + move[i][1]
if 0 <= nx < size and 0 <= ny < size and graph[nx][ny] == 0:
queue.append((nx,ny))
graph[nx][ny] = graph[x][y] + 1
for _ in range(n):
queue = deque([])
size = int(input())
graph = [[0] * size for _ in range(size)]
cx, cy = map(int, sys.stdin.readline().split())
queue.append((cx,cy))
fx, fy = map(int, sys.stdin.readline().split())
bfs(graph, queue, (fx, fy), size)
print(graph[fx][fy])