[BOJ] 7562번:나이트의 이동

■ 문제풀이

1) bfs 알고리즘

 

■ 해답

from collections import deque

t = int(input()) # 테스트 케이스

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

def bfs(current_x, current_y, next_x, next_y):
    queue = deque()
    queue.append([current_x, current_y])
    chess[current_x][current_y] = 1 

    while queue:
        x, y = queue.popleft()
        if x == next_x and y == next_y:
            print(chess[next_x][next_y] - 1)
            return

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

            if 0 <= nx < n and 0 <= ny < n and chess[nx][ny] == 0:
                queue.append([nx, ny])
                chess[nx][ny] = chess[x][y] + 1 
                
for i in range(t):
    n = int(input())
    current_x, current_y = map(int, input().split()) # 현재 체스 위치
    next_x, next_y = map(int, input().split()) # 이동할 체스 위치
    chess = [[0] * n for _ in range(n)]
    bfs(current_x, current_y, next_x, next_y)

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