[백준] 7562번(나이트의 이동)

백준 7562번

최종 제출 코드

import sys
from collections import deque
input = sys.stdin.readline

# 나이트가 이동할 수 있는 좌표
dx = [-2,-2,-1,-1,1,1,2,2]
dy = [-1,1,-2,2,-2,2,-1,1]

repeat = int(input().rstrip())

for k in range(repeat):
  
  n = int(input().rstrip())
  x1, y1 = map(int, input().split()) # 시작점 좌표
  x2, y2 = map(int, input().split()) # 목적지 좌표
  
  queue = deque()
  queue.append([x1, y1])
  # 좌표 방문여부와 시작점으로부터 몇 개의 좌표를 거쳐왔는지 저장할 배열
  visited = [[0 for _ in range(n)] for _ in range(n)]
  
  # 넓이 우선 탐색 실행
  while queue:
    
    x, y = queue.popleft()
    
    if x==x2 and y==y2:
      break
      
    for i in range(8):
      # 이동하고자 하는 좌표가 존재하지 않는다면 continue
      if x+dx[i] < 0 or x+dx[i] >= n or y+dy[i] < 0 or y+dy[i] >= n:
        continue
        
      # 이동하고자 하는 좌표가 존재하며, 아직 방문하지 않은 곳이라면
      # visited 값 업데이트
      if visited[y+dy[i]][x+dx[i]] == 0:
        visited[y+dy[i]][x+dx[i]] = visited[y][x] + 1
        queue.append([x+dx[i], y+dy[i]])
    
  print(visited[y2][x2])