[백준] 16948번 - 데스 나이트

📩 출처

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r1, c1, r2, c2가 주어진다.

출력

첫째 줄에 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

👉 생각

• 간단한 BFS 문제였다. r1, c1을 문제에서 원하는 조건대로 움직이면서 너비우선탐색을 진행한다. 조건에 맞추어 q에 삽입시키고 방문표시를 할 때 이전 위치에서 1을 더해준다. 그렇게 되면 움직인 횟수가 visited에 담기게 된다.
• r2, c2랑 같다면 해당 visited의 값을 반환하고 그렇지 않으면 -1을 반환한다.

from collections import deque
def bfs(x, y):
    q = deque([])
    q.append((x, y))
    visited = [[0] * n for _ in range(n)]
    while q:
        x, y = q.popleft()
        if x == r2 and y == c2:
            return visited[x][y]
        for dx, dy in [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]:
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
    return -1

n = int(input())
r1, c1, r2, c2 = map(int, input().split())

print(bfs(r1, c1))