[백준 7562] 나이트의 이동

문제

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

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

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

 

출력

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

---

접근

나이트가 이동할 수 있는 칸으로만 이동할 수 있도록 방향을 정해주며 BFS로 탐색을 한다.

각 칸으로 이동할 때마다 이전 칸 까지 오는데 이동한 횟수에 + 1을 해주고 목적지에 도착했을 때 BFS를 종료한다.

 

구현

- 현재 나이트의 위치는 start에 목적지는 end 좌표에 저장한다.

- dist는 해당 좌표에 오기까지 나이트가 이동한 횟수를 담고있으며 동시에 방문표시를 할 수 있는 효과가 있다.

- q에 현재 나이트의 위치를 담고 BFS를 시작한다.

- dy, dx는 나이트가 이동할 수 있는 칸으로만 갈 수 있도록 방향을 정해주었다.

N = int(input())
start_y, start_x = map(int, input().split())
end_y, end_x = map(int, input().split())

dist = [[0 for _ in range(N)] for _ in range(N)]
dist[start_y][start_x] = 1
q = deque()
q.append((start_y, start_x))

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

- 현재 좌표를 q에서 꺼내어 목적지라면 BFS를 종료한다.

- 아니라면 이동할 수 있는 8개의 방향을 조사하고 이동할 수 있을 때 q에 넣는다.

- 동시에 dist에 현재 칸 까지 오는데 이동한 횟수에 + 1을 하여 다음 칸에 적용시킨다.

    while q:
        cy, cx = q.popleft()

        if cy == end_y and cx == end_x:
            break

        for d in range(8):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and dist[ny][nx] == 0:
                q.append((ny, nx))
                dist[ny][nx] = dist[cy][cx] + 1

---

전체 코드

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

def check_range(y, x):
    return (0 <= y < N ) and (0 <= x < N)

test_case = int(input())

for _ in range(test_case):
    N = int(input())
    start_y, start_x = map(int, input().split())
    end_y, end_x = map(int, input().split())

    dist = [[0 for _ in range(N)] for _ in range(N)]
    dist[start_y][start_x] = 1
    q = deque()
    q.append((start_y, start_x))

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

    while q:
        cy, cx = q.popleft()

        if cy == end_y and cx == end_x:
            break

        for d in range(8):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and dist[ny][nx] == 0:
                q.append((ny, nx))
                dist[ny][nx] = dist[cy][cx] + 1

    print(dist[end_y][end_x] - 1)