[Baekjoon] 16948번 : 데스 나이트

1. 문제

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

• BFS 문제

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

2. 핵심 아이디어

• 전형적인 BFS 알고리즘 활용

3. Python 문제풀이

import sys
from collections import deque
input = sys.stdin.readline

def bfs(y, x) :
  q = deque()
  q.append((y, x))
  graph[y][x] = 0
  while q :
    y, x = q.popleft()
    for dy, dx in d :
      ny, nx = y + dy, x + dx
      if 0 <= ny < n and 0 <= nx < n and graph[ny][nx] == -1 :
        q.append((ny, nx))
        graph[ny][nx] = graph[y][x] + 1

n = int(input())
r1, c1, r2, c2 = map(int, input().split())
graph = [[-1] * n for _ in range(n)]
d = [(-2, -1), (-2, 1), (0, -2), (0, 2), (2, -1), (2, 1)]
bfs(r1, c1)

print(graph[r2][c2])

4. Java 문제풀이