[백준] 16948번 데스 나이트 - Python / 알고리즘 중급 1/3 - BFS (연습)

ByungJik_Oh·2025년 5월 12일

[Baekjoon Online Judge]

목록 보기

140/244

💡 문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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인 체스판과 두 칸 (r $_1$ , c $_1$ ), (r $_2$ , c $_2$ )가 주어진다. 데스 나이트가 (r $_1$ , c $_1$ )에서 (r $_2$ , c $_2$ )로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

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

입력

첫째 줄에 체스판의 크기 N(5 ≤ N ≤ 200)이 주어진다. 둘째 줄에 r $_1$ , c $_1$ , r $_2$ , c $_2$ 가 주어진다.

출력

첫째 줄에 데스 나이트가 (r $_1$ , c $_1$ )에서 (r $_2$ , c $_2$ )로 이동하는 최소 이동 횟수를 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

💭 접근

7562번 나이트의 이동 문제와 매우 유사한 문제이다. 하지만 일반적인 나이트와 이동방향이 조금 다르기 때문에 이동방향, 즉 dx와 dy를 문제에서 주어진 것과 같이 아래처럼 저장해야한다.

dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]

이후, BFS를 호출하여 각 6개의 방향으로 이동하며 목표지점에 도달하면 중단하고 이동횟수를, 모두 탐색하고 더 이상 이동할 수 있는 지점이 없다면 -1을 출력한다.

📒 코드

import sys
from collections import deque

def bfs():
    q = deque()
    q.append((start_x, start_y))

    dx = [-2, -2, 0, 0, 2, 2]
    dy = [-1, 1, -2, 2, -1, 1]

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

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

            if nx == end_x and ny == end_y:
                print(graph[x][y] + 1)
                sys.exit()

            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == 0:
                graph[nx][ny] = graph[x][y] + 1
                q.append((nx, ny))

n = int(input())
start_x, start_y, end_x, end_y = map(int, input().split())
graph = [[0 for _ in range(n)] for _ in range(n)]

bfs()

print(-1)