백준 16948: 데스 나이트 (Python)

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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번부터 시작한다. 데스 나이트는 체스판 밖으로 벗어날 수 없다.

해설

 너비 우선 탐색(BFS) 로 풀 수 있는 문제이다. 체스 시리즈인 N-queen, 비숍, 나이트의 이동 중에서는 비교적 쉬운 축에 속하는 문제라고 생각한다. 데스 나이트의 이동방향을 dx, dy 에 미리 지정해두고 방향에 따라 움직이며 체스판을 탐색해나가면 된다.

코드

from collections import deque


def BFS(x, y):
    dx = [-2, -2, 0, 0, 2, 2]
    dy = [-1, 1, -2, 2, -1, 1]
    Q = deque()
    Q.append([x, y, 1])
    board[y][x] = 1
    visisted = [[False] * N for _ in range(N)]
    visisted[y][x] = True

    while Q:
        x, y, depth = Q.popleft()
        for i in range(6):
            tx = x + dx[i]
            ty = y + dy[i]

            if tx < 0 or ty < 0 or tx >= N or ty >= N:
                continue

            if tx == r2 and ty == c2:
                return depth

            if not visisted[ty][tx]:
                Q.append([tx, ty, depth+1])
                visisted[ty][tx] = True
                board[ty][tx] = 1
    return -1


N = int(input())
board = [[0]*N for _ in range(N)]
r1, c1, r2, c2 = map(int, input().split())
print(BFS(r1, c1))