[백준7562번] 나이트의 이동 / Python3

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

나의 풀이

2178번 미로 탐색문제와 풀이법이 똑같은 문제였다. 미로 탐색 문제에서는 움직일 수 있는 곳이 상하좌우이지만 해당 문제는 나이트의 이동인 것만 고려해주고 BFS를 돌려주면 최단거리를 쉽게 구할 수 있다. BFS의 장점이 바로 최단거리들을 저장해주는다는 것을 이용하는 것이다.

• 나이트의 이동가능한 곳

  (예를들어 원점을 (2,2)라고 가정해보자.)
  
  - 이동할 수 있는 위치       x       y
          (0,1), (0,3)  =>   -2  | -1, +1
          (1,0), (1,4)  =>   -1  | -2, +2
          (3,0), (3,4)  =>   +1  | -2, +2
          (4,1), (4,3)  =>   +2  | -1, +1

  위와 같이 이동할 수 있는 위치에 대한 x와 y좌표의 변화를 정리한다면 상하좌우를 구해줄때 사용하던 dx=[-1,0,1,0], dy=[0,-1,0,1]과 같이 정해놓을 수 있다.

  나이트의 이동가능한 곳은 총 8곳으로 dx와 dy를 쓰면 다음과 같다.

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

이제 나이트의 이동경로를 구했으니 미로 탐색 문제와 똑같이 BFS를 돌리고나서 목표로 정해진 좌표의 값을 출력해주면 그것이 바로 최단으로 갈 수 있는 이동 횟수이다.

코드

# 7562번 나이트의 이동
from collections import deque
import sys

# bfs
def check(board, x, y):
    q = deque()
    q.append([x,y])

    # 나이트가 이동할 수 있는 8가지의 경우
    dx = [-2, -2, -1, -1, 1, 1, 2, 2]
    dy = [-1, 1, -2, 2, -2, 2, -1, 1]
    while q:
        x, y = q.popleft()

        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n:
                if board[ny][nx] == -1:
                    # 방문하지 않은 곳이면 바로 이전의 움직임 +1을 저장
                    board[ny][nx] = board[y][x] + 1
                    q.append([nx,ny])

# main
T = int(input())

for _ in range(T):
    n = int(input())

    # 방문하지 않은 곳 : -1
    board = [[-1 for _ in range(n)] for _ in range(n)]
    cur_x, cur_y = [int(x) for x in sys.stdin.readline().split()]
    target_x, target_y = [int(x) for x in sys.stdin.readline().split()]

    board[cur_y][cur_x] = 0

    # bfs 실행
    check(board, cur_x, cur_y)
    print(board[target_y][target_x])