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

난이도 : 실버 1
유형 : BFS 너비 우선 탐색
https://www.acmicpc.net/problem/7562

문제 접근

체스판 위에 나이트가 있다.
이 나이트를 목표 위치까지 최소 몇 번 이동시켜야 하는지 구하는 문제다.

나이트는 체스에서 아래 8방향으로 움직일 수 있다.
그래서 단순한 DFS보단 최단거리를 보장하는 BFS를 써야 한다.

BFS는 움직일 수 있는 경로를 항상 간선(edge)이라고 생각하고 for문 돌려주는 것이 중요한 것 같다.

• 체스판의 크기 I x I를 입력받는다.
• 시작 좌표와 도착 좌표를 입력받는다.
• 나이트의 이동 방식은 총 8가지 방향이 있다 → dx, dy 설정.
• 각 위치를 방문할 때 몇 번째 이동인지를 distance 배열에 저장한다.
• BFS를 통해 도착 위치에 도달하면, 해당 위치의 distance 값을 출력한다.

해답 및 풀이

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

# 나이트가 이동할 수 있는 8가지 방향
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

T = int(input())  # 테스트 케이스 수

for _ in range(T):
    I = int(input())  # 체스판 크기
    start_x, start_y = map(int, input().split())
    end_x, end_y = map(int, input().split())

    visited = [[False] * I for _ in range(I)]
    distance = [[0] * I for _ in range(I)]

    queue = deque()
    queue.append((start_x, start_y))
    visited[start_x][start_y] = True

    while queue:
        x, y = queue.popleft()

        # 목표 지점에 도착했다면 종료
        if x == end_x and y == end_y:
            print(distance[x][y])
            break

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

            if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]:
                visited[nx][ny] = True
                distance[nx][ny] = distance[x][y] + 1
                queue.append((nx, ny))