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

문제

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

7562번: 나이트의 이동

---

문제 요약

l × l 크기의 체스판 위에 나이트 한 개가 있다.

 

현재 나이트의 위치와 나이트가 이동하려는 위치를 입력 받고, 최소 몇 번만에 이동할 수 있는지를 출력한다.

---

코드

from collections import deque

t = int(input())

# 나이트가 이동할 수 있는 경우의 수
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

for _ in range(t):
    l = int(input()) # 체스판 한 변의 길이

    board = [[0] * l for _ in range(l)]
    # 해당 인덱스(칸)에 나이트가 현재 위치에서 몇 번만에 이동할 수 있는지 저장하는 배열
 
    cur = list(map(int, input().split()))
    goal = list(map(int, input().split()))

    # 큐를 이용한 bfs 탐색
    q = deque()
    q.append(cur)

    while True:
        x, y = q.popleft()
        
        # 현재 탐색 중인 위치가 목표 위치라면 출력 후 종료
        if x == goal[0] and y == goal[1]:
            print(board[x][y])
            break
        
        # 나이트가 이동할 수 있는 모든 경우의 수를 탐색 후 board 이동 횟수 저장
        for d in range(8):
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx and 0 <= ny and nx < l and ny < l and board[nx][ny] == 0:
                board[nx][ny] = board[x][y] + 1
                q.append([nx, ny])

---

코드 설명

1. 나이트가 이동할 수 있는 경우의 수를 dx, dy 배열을 통해 표현한다.

 

2. 체스판과 같은 크기의 2차원 배열 board를 정의한다.

 

3.  큐를 이용한 BFS(넓이 우선 탐색)을 통해 현재 나이트 칸에서 [x, y]칸까지 몇 번 이동하여 도착할 수 있는지 board[x][y]에 저장한다.

 

4. x, y가 목표 지점일 경우 board[x][y]를 출력하고 탐색을 종료한다.