백준 16948 파이썬 - 데스 나이트

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

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번부터 시작한다.

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

코드

import sys
from collections import deque
n = int(sys.stdin.readline())
r1, c1, r2, c2 = map(int, sys.stdin.readline().split())
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]
visited = [[-1] * n for _ in range(n)]
def bfs():
    q = deque()
    q.append((r1, c1))
    visited[r1][c1] = 0
    while q:
        r, c = q.popleft()
        for i in range(6):
            nr = r + dx[i]
            nc = c + dy[i]
            if 0 <= nr < n and 0 <= nc < n and visited[nr][nc] == -1:
                q.append((nr, nc))
                visited[nr][nc] = visited[r][c] + 1
                if nr == r2 and nc == c2:
                    return visited[r2][c2]
    return -1
print(bfs())

풀이

visited 배열에 움직인 횟수를 저장하고, 계속 움직일 수 있는 곳으로 움직이며 안가본 곳이면 q에 더해주고 움직인 횟수를 갱신한다. nr과 nc가 최종적으로 가고 싶은 곳이 되면 바로 출력해준다.