백준 16948 - 데스 나이트 - 2021/04/15

문제 설명

 

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (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문제로 visited를 만들어 방문 횟수를 출력하면 된다. 상하좌우가 아니라 육각형모양의 방향으로 6군데를 방문할 수 있으며 방문할 수 없는 경우 -1을 출력한다.

 

import sys
input=sys.stdin.readline

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]
from collections import deque
q = deque()
q.append((r1, c1))
visited = [[0] * n for i in range(n)]
while q:
    x, y = q.popleft()
    if x == r2 and y == c2:
        print(visited[x][y])
        break
    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx <= -1 or nx >= n or ny <= -1 or ny >= n:
            continue
        if visited[nx][ny] == 0:
            visited[nx][ny] = visited[x][y] + 1
            q.append((nx, ny))
if visited[r2][c2]==0:
    print(-1)