[백준][Python][7562][BFS] 나이트의 이동

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

7562번: 나이트의 이동

BFS 문제다.

 

전형적인 길찾기 문제에서 움직이는 위치만 달라진 문제다.

원래 십자모양으로 움직일 때는 dx = [1,-1,0,0], dy=[0,0,1,-1] 이런 식으로 했는데

이 움직이는 숫자만 달라진다.

 

 

import sys
from collections import deque

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

T = int(sys.stdin.readline())

for _ in range(T):
    q = deque()
    size = int(sys.stdin.readline())
    x, y = [int(i) for i in sys.stdin.readline().split()]
    cx, cy = [int(i) for i in sys.stdin.readline().split()]

    q.append([x, y, 0])

    v = [[False]*size for _ in range(size)]
    v[y][x] = True

    while q:
        tx, ty, tt = q.popleft()

        if cx == tx and cy == ty:
            print(tt)
            break

        for i in range(8):
            if 0 <= tx+dx[i] < size and 0 <= ty+dy[i] < size and not v[ty+dy[i]][tx+dx[i]]:
                q.append([tx+dx[i], ty+dy[i], tt+1])
                v[ty+dy[i]][tx+dx[i]] = True