220302 - 나이트의 이동

◾ 나이트의 이동 : 백준 7562번

• https://www.acmicpc.net/problem/7562

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

---

입력

• 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
• 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

• 각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

입출력 예

Input	Output
3 8 0 0 7 0 100 0 0 30 50 10 1 1 1 1	5 28 0

---

◾ 풀이

1. 해설

• BFS 알고리즘을 통해 해결할 수 있다.
• 나이트는 8개의 이동 방향을 가지고 있다.
  • (행, 열) : (2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)
  • 방문한 노드를 표시하며 목표 지점까지 탐색한다.

---

2. 프로그램

1. t(테스트 케이스) 입력
2. i, 나이트 좌표, 목표 좌표 입력
3. 현재 좌표 points(deque)에 추가, 방문 표시
4. BFS 알고리즘을 통해 좌표까지 최단 거리 탐색

# 코드
# import sys
from collections import deque

# input = sys.stdin.readline

t = int(input())

for _ in range(t):
    i = int(input())
    start_r, start_c = map(int, input().split(' '))
    end_r, end_c = map(int, input().split(' '))
    visited = {}
    points = deque([])
    answer = 0

    points.append((start_r, start_c, 0))
    visited[(start_r, start_c)] = True
    while points:
        r_, c_, cnt = points.popleft()
        if r_ == end_r and c_ == end_c:
            answer = cnt
            break
        for d_r, d_c in [(2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1)]:
            new_r = r_ + d_r
            new_c = c_ + d_c

            if new_r < 0 or new_r >= i or new_c < 0 or new_c >= i:
                continue
            if (new_r, new_c) not in visited:
                points.append((new_r, new_c, cnt+1))
                visited[(new_r, new_c)] = True
    print(answer)

• Input
  3
  8
  0 0
  7 0
  100
  0 0
  30 50
  10
  1 1
  1 1