[BOJ 7562] 나이트의 이동 (Python)

풀이

주말에 여행을 다녀오느라 알고리즘을 쉬었다...ㅜㅜ 힐링 풀충전 했으니 이 기운을 알고리즘 문제 푸는 데 다 쏟아보려 한다.~ 다시 주제를 바꿔 제 문제 풀이 방법을 포스팅 하려한다.

이 문제는 큐를 이용한 BFS 기초를 구현할 수 있는지를 물어보는 문제라고 생각한다. BFS 개념을 알고, 혼자서 구현할 수 있다면 쉽게 풀 수 있을 것으로 생각한다. 단, 주의할 점은 보통의 BFS 문제에서는 4방 탐색을 주로 수행하지만, 위 문제는 8방 탐색을 수행한다는 점이다. 간략하게 로직을 설명하겠다.

1. 나이트가 있는 현재 x, y 좌표와 나이트의 도착점 x, y 좌표가 같은지 확인한다.

2. 같지 않다면 나이트를 기준으로 8방 탐색을 수행한다. (도착점에 도달할 때까지 탐색 반복한다.)

3. 도착점에 도달했다면 종료하고 나이트가 몇 번 움직였는지 반환한다.

코드

import sys
from collections import deque

input = sys.stdin.readline
T = int(input())
dir = [[-2, -1], [-1, -2], [2, -1], [1, -2], [2, 1], [1, 2], [-2, 1], [-1, 2]]


def bfs(arr, sx, sy, ex, ey):
    if sx == ex and sy == ey:
        return 0

    q = deque([(sx, sy)])
    arr[sx][sy] = 1
    ans = 1

    while q:
        size = len(q)
        # 나이트가 최소 몇 번 움직이는지 구해주기 위한 for 문
        for s in range(size):
            x, y = q.popleft()
            for i in range(8):
                nx, ny = x + dir[i][0], y + dir[i][1]
                if nx == ex and ny == ey:
                    return ans

                elif 0 <= nx < len(arr) and 0 <= ny < len(arr) and not arr[nx][ny]:
                    arr[nx][ny] = 1
                    q.append((nx, ny))

        ans += 1

    return ans


for _ in range(T):
    I = int(input())

    chess = [[0] * I for _ in range(I)]
    startX, startY = map(int, input().split())
    endX, endY = map(int, input().split())

    print(bfs(chess, startX, startY, endX, endY))