[백준] 7562번 나이트의 이동 (Python)

풀이

---

체스판 위의 나이트가 일정 지점에서 목표 지점으로 이동하는 최소한의 이동횟수를 구하는 문제이다.

나이트의 이동경로방향을 dx, dy 를 통해 선언해준 뒤 입력조건에 맞춰 BFS 를 실행한다.

나이트가 이동할 때 마다 방문처리를 해주면서 몇 번째 이동으로 인해 방문했는지 2차원 배열 board 에 저장한 뒤,

목표 지점에 도달했을 때의 값을 반환해주면된다.

소스코드

---

# 나이트의 이동
from collections import deque
import sys
input = sys.stdin.readline
 
def bfs(i, j):
    q = deque()
    q.append([i, j])
    board[i][j] = 1  # 시작 점 방문처리
    while q:
        x, y = q.popleft()
        if x == c and y == d:
            return board[x][y] - 1
        for k in range(8):
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < l and 0 <= ny < l and board[nx][ny] == 0:  # 범위 내 이면서 방문하지 않았을 경우
                board[nx][ny] = board[x][y] + 1  # 방문 처리 겸 초 계산
                q.append([nx, ny])
 
dx = [-1, -2, -2, -1, 1, 2, 2, 1]
dy = [-2, -1, 1, 2, 2, 1, -1, -2]
 
for t in range(int(input())):
    l = int(input())
    board = [[0] * l for _ in range(l)]
    a, b = map(int, input().split())
    c, d = map(int, input().split())
    print(bfs(a, b))

References

---

• BOJ 7562 - 나이트의 이동