BFS(데스 나이트/S1) - 16948

1. 문제

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

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

2. 입력

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

 

7
6 6 0 1

 

6
5 1 0 5

 

7
0 3 4 3

 

3. 출력

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

 

4

 

-1

 

2

 

4. 코드

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
r1,c1,r2,c2 = map(int,input().split())
visited = [[0]*n for _ in range(n)]
mx = [-2,-2,0,0,2,2]
my = [-1,1,-2,2,-1,1]

def bfs():
  q = deque()
  visited[r1][c1] = 1
  q.append((r1,c1))
  while q:
    x,y = q.popleft()
    # 체스 말이동
    for i in range(6):
      dx,dy = x+mx[i],y+my[i]
      if 0 <= dx < n and 0 <= dy < n and visited[dx][dy] == 0:
        visited[dx][dy] = visited[x][y] + 1
        q.append((dx,dy))
   
bfs()
# 시작점의 1을 감소
print(visited[r2][c2]-1)

 

5. 풀이설명