백준) 나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

from collections import deque

a = int(input())

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

answer = []
      
for _ in range(a):
  row = int(input())
  now = list(map(int,input().split()))
  forward = list(map(int,input().split()))

  arr = [[0 for _ in range(row)] for _ in range(row)]
  arr[now[0]][now[1]] = 1
  q = deque()
  q.append((now[0],now[1]))
  

  while q:
    x,y = q.popleft()
    if x == forward[0] and y == forward[1]:
      break

    for i in range(len(dy)):
      nx = dx[i] + x
      ny = dy[i] + y
      if 0 <= nx < row and 0 <= ny < row:
        if arr[nx][ny] == 0:
          arr[nx][ny] = arr[x][y] + 1
          q.append((nx,ny))
          
    
  print(arr[forward[0]][forward[1]] - 1)

전형적인 bfs 알고리즘 문제이다.

나이트가 이동할 수 있는 8방향을 모두 정하고

맨처음 서있는 칸을 1,

다음에 움직일 수 있는 칸들을 현재칸 + 1로 설정한다.

만일 목적지에 도달하지 못할 경우 목적지의 숫자는 0이되고,

목적지의 도달했다면 목적지의 숫자는 정답 +1이 된다.