[BOJ] 7562 | 나이트의 이동

아래 백준 로고를 클릭하면 해당 문제로 이동합니다 😀

풀이과정

---

그림에서 보면 나이트가 이동할 수 있는 좌표는 현재 좌표를 기준으로 다음과 같다.

>>> [-2, 1], [-2, -1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]

BFS를 통해 해당 좌표들을 돌아보면서 목표 좌표가 나올 때 까지 좌표를 방문하면 된다.

코드

---

import sys
from collections import deque

T = int(input())
directions = [[-2, 1], [-2, -1], [-1, 2], [-1, -2], [1, 2], [1, -2], [2, 1], [2, -1]]

def bfs():
    q = deque()
    q.append([start_x, start_y])

    while q:
        x, y = q.popleft()

        if x == end_x and y == end_y:
            return maps[x][y]

        for dx, dy in directions:
            mx, my = x + dx, y + dy
            if 0 <= mx < I and 0 <= my < I and not maps[mx][my]:
                maps[mx][my] = maps[x][y] + 1
                q.append([mx, my])

for i in range(T):
    I = int(sys.stdin.readline().rstrip())

    start_x, start_y = map(int, sys.stdin.readline().split())
    end_x, end_y = map(int, sys.stdin.readline().split())

    maps = [[0] * I for _ in range(I)]

    result = bfs()
    print(result)

결과

---