PS/백준

실버1 나이트의 이동(7562)

jjw000628 2023. 12. 22. 15:23
 

7562번: 나이트의 이동

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수

www.acmicpc.net

처음 이문제를 풀었는데 계속 답이 나오지 않았다. matrix를 출력해보니 한 방향으로 가지 않는 것이였다. 그래서 살펴보니 directions의 배열에 잘못 입력을 해서 문제였다. 배열을 잘 고쳐서 8방향 전부 갈 수 있게 만들어 풀 수 있었다.

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

directions = [(-2, -1), (-1, -2), (2, 1), (1, 2), (-2, 1), (-1, 2), (2, -1), (1, -2)]

def bfs(startX, startY, destX, destY):
  queue = deque([(startX, startY)])
  matrix[startX][startY] = 1 # matrix 증가 시키자!
  while queue:
    v = queue.popleft()
    for d in directions:
      nextX, nextY = v[0]+d[0], v[1]+d[1]
      if (0<=nextX<n and 0<=nextY<n) and not matrix[nextX][nextY]:
        queue.append((nextX, nextY))
        matrix[nextX][nextY] = matrix[v[0]][v[1]] + 1
        if (nextX, nextY) == (destX, destY): return matrix[destX][destY] - 1

for _ in range(int(input())):
  n = int(input())
  matrix = [[0]*n for _ in range(n)]
  startX, startY = map(int, input().split())
  destX, destY = map(int, input().split())
  if (startX, startY) == (destX, destY): print(0)
  else: print(bfs(startX, startY, destX, destY))