[백준] 7562 - 나이트의 이동

문제

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

---

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

---

예제 입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력

5
28
0

---

해결 방법

from collections import deque

t = int(input())


def checkValid(y, x, l):
    return 0 <= y < l and 0 <= x <l


for test_case in range(1, t+1):
    l = int(input()) # 체스판의 길이
    current_pos = list(map(int, input().split()))
    destination = list(map(int, input().split()))

    movements = [[+2, +1], [-2, +1], [+1, +2], [-1, +2],
                 [+2, -1], [-2, -1], [+1, -2], [-1, -2]]

    queue = deque()
    visited = [[0 for _ in range(l)] for _ in range(l)]
    queue.append(current_pos)

    while queue:
        y, x = queue.popleft()
        if [y, x] == destination:
            print(visited[y][x])
            break
        for move in movements:
            ny, nx = y + move[0], x + move[1]
            if checkValid(ny, nx, l) and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                queue.append((ny, nx))