[BOJ] 백준 7562번 나이트의 이동 - 파이썬(Python)

문제

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

입력

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

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

출력

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

 

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

7562번: 나이트의 이동

 

💡 풀이 및 코드

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

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

n = int(input())
result = []
for _ in range(n):
    k = int(input())
    xs, ys = map(int, input().split())
    xe, ye = map(int, input().split())
    
    queue = deque()
    graph = [[-1]*k for _ in range(k)]
    queue.append((xs, ys))
    graph[xs][ys] = 0
    while queue:
        x, y = queue.popleft()
        for j in range(8):
            nx = x + dx[j]
            ny = y + dy[j]
            if nx < 0 or nx >= k or ny < 0 or ny >= k:
                continue
            if graph[nx][ny] != -1:
                continue
            graph[nx][ny] = graph[x][y] + 1
            queue.append((nx, ny))
        if graph[xe][ye] != -1:
            break
    result.append(graph[xe][ye])

for r in result:
    print(r)

BFS방식으로 나이트가 이동할 수 있는 경로를 이동하며 이동횟수를 기록한다. 나이트 이동 후 이동 횟수는 이전에 나이트가 있었던 위치까지의 이동횟수(graph[x][y])에 1을 더한 값으로 표현한다. 시간초과를 해결하기 위해 목적지에 도달 했을 경우 더이상 while문을 돌지 않도록 break 처리를 해주었다.