[백준] 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

풀이

bfs-큐 개념을 이용한 일반적인 문제였다. 나이트가 "최소" 몇 번만에 이동할 수 있는지를 구하는 문제이기 때문에 bfs-큐 풀이를 떠올려야 한다.

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

def useableArr(r,c,n):
    arr = []
    if(r-2 >= 0 and c+1 <= n-1): arr.append([r-2,c+1])
    if(r-1 >= 0 and c+2 <= n-1): arr.append([r-1,c+2])
    if(r+1 <= n-1 and c+2 <= n-1): arr.append([r+1,c+2])
    if(r+2 <= n-1 and c+1 <= n-1): arr.append([r+2,c+1])
    if(r+2 <= n-1 and c-1 >= 0): arr.append([r+2,c-1])
    if(r+1 <= n-1 and c-2 >= 0): arr.append([r+1,c-2])
    if(r-1 >= 0 and c-2 >= 0): arr.append([r-1,c-2])
    if(r-2 >= 0 and c-1 >= 0): arr.append([r-2,c-1])
    return arr

def bfs(size, start, end):
    visited = [[0 for _ in range(size)] for _ in range(size)]
    queue = deque()
    sx, sy = map(int, start)
    ex, ey = map(int, end)
    queue.append([sx, sy]) # 시작 좌표 큐에 삽입
    visited[sx][sy] = 0 # 시작 좌표 방문처리

    while queue:
        sa = queue.popleft()
        x, y = map(int, sa)
        if x == ex and y == ey: 
            print(visited[x][y])
            return 

        ua = useableArr(x,y,size) # 유효하면서 방문안한 좌표들 모은 배열
        for d in ua:
            if visited[d[0]][d[1]] == 0:
                queue.append(d) # 좌표 큐에 삽입
                visited[d[0]][d[1]] = visited[x][y] + 1 # 해당 좌표 방문처리

n = int(input())
for _ in range(n):
    size = int(input())
    start = input().split()
    end = input().split()
    bfs(size, start , end)