[백준] 7562 나이트의 이동

문제

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

입력

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

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

출력

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

내 풀이

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

def BFS(queue, visited, start, goal, dx, dy):
    queue.append(start)
    visited[start[0]][start[1]]
    
    while queue:
        x, y = queue.popleft()
        
        if x == goal[0] and y == goal[1]:
            return 0
        
        for i in range(8):
            nx = x+dx[i]
            ny = y+dy[i]
            
            if nx < 0 or nx >= size or ny < 0 or ny >= size:
                continue
            
            if nx == goal[0] and ny == goal[1]:
                visited[nx][ny] == True
                return chess[x][y]+1
            
            if visited[nx][ny] == False:
                queue.append([nx, ny])
                visited[nx][ny] = True
                chess[nx][ny] = chess[x][y]+1
                
dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, 2, 1, -1, -2]

n = int(input())

for i in range(n):
    size = int(input())
    start = list(map(int, input().split())) 
    goal = list(map(int, input().split()))
    
    chess = [[0]*size for _ in range(size)]
    visited = [[False]*size for _ in range(size)]
    
    queue = deque()
    
    answer = BFS(queue, visited, start, goal, dx, dy)
    
    print(answer)

코멘트

체스에 대해 전혀 몰라서 나이트의 이동 방식만 읽었는데도 식은 땀을 흘렸지만 침착하게 살펴보니 출발 지점으로부터 (+1, +2), (+2, +1), (+2, -1), (+1, -2), (-1, +2), (-2, +1), (-2, -1), (-1, -2) 이 8가지 이동 중 하나를 취한다는 것을 알 수 있었다. 그러나 이 8가지 중 어떤 것을 취해서 최소 이동 횟수로 출발점에서 목적지까지 도달할 수 있을지 모르겠어서 멘붕. 그러다 결국 다른 사람의 풀이를 참고하고 나서야 BFS로 구현해서 풀어야 한다는 것을 알았다.
그러나 아직까지 어떤 원리로 이를 BFS로 풀었을 때 최소 이동 횟수를 구할 수 있는지 모르겠다.

References

https://www.acmicpc.net/problem/7562
https://velog.io/@falling_star3/백준Python-7562번-나이트의-이동