[백준] 7562번 나이트의 이동 파이썬

문제

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

5
28
0

제출 답안

1. 기존에는 bfs가 상하좌우로 대부분 이동하였다.
2. 이 문제에서는 그 방향의 좌표만 수정하면 된다.
3. 그런 후 방문 할 때마다 해당 칸에 방문한 횟수 + 1 하면 된다.
   1. 어차피 0으로 초기화해서 방문했던 칸은 다시 방문하지 않기에 최초 방문한 경우가 최소 경우가 된다.

'''
1. 아이디어
- dy, dx를 기존과는 다르게, 다른것은 bfs 그대로
2. 시간 복잡도
- O(V+E)
- V : IxI
- E : 4V
= 5V = 5x300x300 = 450,000 < 2억
3. 자료구조
int [][]
bool [][]
'''

import sys
from collections import deque

input = sys.stdin.readline
dy = [-2, -1, 1, 2, 2, 1, -1, -2]
dx = [1,2,2,1,-1,-2,-2,-1]
n = int(input())

def bfs(y, x, m):
    q = deque([(y, x)])
    while q:
        cy, cx = q.popleft()
        for k in range(8):
            ny = cy + dy[k]
            nx = cx + dx[k]
            if 0<=ny<m and 0<=nx<m:
                if distance[ny][nx] == 0:
                    distance[ny][nx] = distance[cy][cx] + 1
                    q.append((ny, nx))
answer = []
for _ in range(n):
    m = int(input())
    distance = [[0] * m for _ in range(m)]
    start_y, start_x = map(int, input().split())
    target_y, target_x = map(int, input().split())
    if start_y != target_y or start_x != target_x:
        bfs(start_y, start_x, m)
    answer.append(distance[target_y][target_x])

for i in answer:
    print(i)