[Python | 7562] 나이트의 이동

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

---

문제 설명

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

 

📌 시간 제한: 1초

---

입력

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

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

---

출력

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

---

문제 접근

체스판 위에서 나이트가 한 위치에서 다른 위치로 이동할 때, 최소 몇 번만에 도달할 수 있는지를 묻는 문제다. 나이트는 "ㄱ"자 형태로 총 8가지 방향으로 움직일 수 있고, 체스판의 크기 l, 시작 위치 (x1, y1), 목표 위치 (x2, y2)가 입력으로 주어진다. 이때 목표 위치까지 이동하는 데 필요한 최소 이동 횟수를 구하는 것이 목적이다.

문제를 보면 이동에 가중치가 없고, 최소 이동 횟수를 구하는 구조이기 때문에 BFS(너비 우선 탐색)이 바로 떠오른다. 체스판을 2차원 배열로 보고 각 칸을 하나의 노드로 간주하며, 나이트가 갈 수 있는 다음 위치들을 그래프의 간선처럼 연결해 탐색을 수행한다.

 

방법

• 나이트의 이동은 8가지 방향으로 정의된다.
  → dx = [2, 1, -1, -2, -2, -1, 1, 2]
  → dy = [1, 2, 2, 1, -1, -2, -2, -1]
• 시작 위치에서부터 BFS를 돌리며, visited[x][y] 배열을 통해
  → 방문 여부 + 이동 횟수를 함께 관리한다.
• 도착 지점에 처음 도달하는 순간이 곧 최단 거리이므로
  → 그 값을 출력하고 탐색을 종료하면 된다.

시간 복잡도

• 한 테스트케이스에서 방문 가능한 칸은 최대 l × l
• 각 칸은 한 번만 방문하므로
  → O(l²)
• 테스트케이스가 T개 주어지므로 전체 복잡도는
  → O(T × l²)
• 최대 300 × 300 × 100 = 9,000,000 → 파이썬으로 충분히 처리 가능

---

구현

• visited 배열에 이동 횟수를 저장하는 방식으로, 거리 계산과 방문 여부를 동시에 처리
• 시작 지점을 1로 초기화했기 때문에, 출력할 때는 -1을 해준다
• 도착 좌표에 도달하면 즉시 break 하므로, 불필요한 탐색이 없다

from collections import deque

# 나이트의 8가지 이동 방향 정의 (x, y 좌표 변화)
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):
    l = int(input())  # 체스판 한 변의 길이
    x1, y1 = map(int, input().split())  # 시작 위치
    x2, y2 = map(int, input().split())  # 목표 위치

    # 방문 여부 및 이동 횟수를 기록할 2차원 배열
    visited = [[0] * l for _ in range(l)]

    queue = deque()
    queue.append((x1, y1))  # 시작 위치 큐에 삽입
    visited[x1][y1] = 1     # 시작 위치 방문 처리 (이동 횟수 1로 시작)

    while queue:
        x, y = queue.popleft()  # 현재 위치

        # 목표 지점에 도달하면 이동 횟수 출력 후 종료
        if x == x2 and y == y2:
            print(visited[x][y] - 1)  # 시작점을 1로 했으므로 -1 보정
            break

        # 8방향으로 이동 가능한 좌표 탐색
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            # 체스판 범위 내 && 아직 방문하지 않은 위치라면 이동
            if 0 <= nx < l and 0 <= ny < l and visited[nx][ny] == 0:
                visited[nx][ny] = visited[x][y] + 1  # 이동 횟수 갱신
                queue.append((nx, ny))  # 다음 위치 큐에 추가

 

위처럼 일반적으로 BFS는 큐를 이용해 레벨 순서대로 탐색을 진행한다. 하지만 이 문제처럼 이동 범위가 제한적이고, 레벨 단위 탐색이 필요한 경우에는 큐 없이도 BFS를 재귀적으로 구현할 수 있다.

이 코드에서는 각 재귀 호출이 하나의 탐색 레벨에 해당하며, 현재 레벨의 위치들을 리스트로 묶어 반복문으로 순회한 뒤, 다음 레벨에 해당하는 좌표들을 새 리스트에 담아 재귀로 넘긴다. 이 과정을 통해 큐 없이도 BFS의 핵심인 레벨 순 탐색을 자연스럽게 유지할 수 있다.

다만 이는 큐를 명시적으로 사용하지 않고, 리스트와 재귀 호출로 그 동작을 흉내낸 구조로 볼 수 있다. BFS의 논리는 따르지만 전통적인 구현은 아니며, 특히 탐색 깊이가 깊어질 경우에는 파이썬의 재귀 호출 제한 때문에 비효율적일 수 있다는 점도 고려해야 한다.

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

# 재귀적으로 BFS 수행
def bfs_recursive(current_level, visited, x2, y2, l, depth):
    next_level = []  # 다음 레벨에서 탐색할 좌표들 저장
    for x, y in current_level:
        if x == x2 and y == y2:
            print(depth)  # 목표 지점 도달 시 현재 깊이 출력
            return True
        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            # 체스판 범위 내이며 방문하지 않은 좌표라면 이동
            if 0 <= nx < l and 0 <= ny < l and not visited[nx][ny]:
                visited[nx][ny] = True
                next_level.append((nx, ny))
    if not next_level:
        return False  # 다음 탐색할 좌표가 없으면 종료
    return bfs_recursive(next_level, visited, x2, y2, l, depth + 1)  # 다음 레벨 탐색

T = int(input())  # 테스트케이스 수 입력
for _ in range(T):
    l = int(input())  # 체스판 크기
    x1, y1 = map(int, input().split())  # 시작 좌표
    x2, y2 = map(int, input().split())  # 목표 좌표

    visited = [[False] * l for _ in range(l)]  # 방문 여부 배열
    visited[x1][y1] = True  # 시작 위치 방문 처리
    bfs_recursive([(x1, y1)], visited, x2, y2, l, 0)  # 재귀 BFS 시작