[BOJ/백준] 16948번 데스 나이트 (Python 파이썬)

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

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

입력

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

출력

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

예제 입력 1 

7
6 6 0 1

예제 출력 1 

4

예제 입력 2 

6
5 1 0 5

예제 출력 2 

-1

예제 입력 3 

7
0 3 4 3

예제 출력 3 

2

 

---

풀이

우선 이전에 풀이했던 "나이트의 이동" 문제와 유사합니다. 다만 해당 문제에서는 8가지 경우의 수가 아닌 6가지 경우의 수가 주어졌습니다. 

https://great-park.tistory.com/108

[BOJ/백준] 7562번 나이트의 이동 (Python 파이썬)

 

우선 데스 나이트의 이동 방향을 나타내면 아래와 같습니다.

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

입력으로 시작 위치와 목표 위치가 주어졌습니다. 따라서, 시작 위치에서 BFS을 실시하고 목표 위치에 도달하면 이동 횟수를 리턴하며 탐색을 종료하고, 그렇지 않다면 탐색을 반복하다가 더이상 탐색이 불가능한 경우(큐가 빔) -1을 리턴하고 종료하면 됩니다.

 

Code

import sys
from collections import deque
input = sys.stdin.readline
# 데스 나이트의 이동 방향
dx = [-2, -2, 0, 0, 2, 2]
dy = [-1, 1, -2, 2, -1, 1]

N = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]

R1, C1, R2, C2 = map(int, input().split())


def BFS(x, y):
    queue = deque([(x, y)])
    graph[y][x] = 1
    while queue:
        x, y = queue.popleft()

		# 탐색 종료 조건 -> target을 잡으면 종료한다.
        if x == R2 and y == C2:
            return graph[y][x] - 1

        for i in range(6):
            next_x, next_y = x + dx[i], y + dy[i]
            if 0 <= next_x < N and 0 <= next_y < N: # 범위 확인
                if graph[next_y][next_x] == 0:   # 진입 가능 여부 확인
                    queue.append([next_x, next_y])
                    graph[next_y][next_x] = graph[y][x] + 1
    return -1 #못 잡을 시 종료


print(BFS(R1, C1))