100년 뒤 개발자 한승규입니다.

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

원래 상하좌우 4방향만 움직이던 그래프에서 나이트가 이동하는 8방향으로 이동 할 수 있도록 방향을 설정해주면 된다.

여기에는 못 가는 경우가 있을 줄 알았는데... 고려하지 않고 그냥 제출해도 맞다고 되는 것을 보니, 못 가는 경우가 존재하지 않는 것 같다.

그냥 Python3로 제출하면 시간초과가 발생하고 Pypy3로 제출했었다.

그냥 방향만 추가가 되었고, 푸는 방법은 기존과 다르지 않으니 더 설명은 하지 않도록 하겠다.

from collections import deque
import sys

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

for _ in range(int(sys.stdin.readline())):
    i = int(sys.stdin.readline().strip())

    start_y, start_x = map(int, sys.stdin.readline().split())

    dest_y, dest_x = map(int, sys.stdin.readline().split())

    visited = [[float('inf') for _ in range(i)] for _ in range(i)]
    visited[start_y][start_x] = 0

    need_visit = deque()

    need_visit.append([0, start_y, start_x])

    result = -1

    while need_visit:

        cur_cnt, cur_y, cur_x = need_visit.popleft()

        if cur_y == dest_y and cur_x == dest_x:
            result = cur_cnt

        for index in range(8):
            next_y, next_x = cur_y + dy[index], cur_x + dx[index]
            if 0 <= next_y < i and 0 <= next_x < i and visited[next_y][next_x] > cur_cnt + 1:
                need_visit.append([cur_cnt + 1, next_y, next_x])
                visited[next_y][next_x] = cur_cnt + 1

    print(result)