[BOJ] 7562. 나이트의 이동

📌 문제 제목

문제 링크: BOJ 7562

---

🗒️ 문제 설명

체스판 위에 한 나이트가 놓여져 있다. 나이트가 이동하려고 하는 칸이 주어진다.

나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

---

💡 문제 해결 아이디어

• 나이트의 이동 direction을 정의
• dist 배열을 만들어서 이동한 적 없는 좌표에 대해서만 움직인다.

---

⌛️ 시간 복잡도

• O(T x L^2)

---

✅ 최종 코드

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

T = int(input().strip())

direction = [(-2, 1), (-1, 2), (1, 2), (2, 1),
             (2, -1), (1, -2), (-1, -2), (-2, -1)]


def bfs(s_x, s_y, e_x, e_y, dist):
    queue = deque([(s_x, s_y)])
    while queue:
        xp, yp = queue.popleft()
        if xp == e_x and yp == e_y:
            break
        for dx, dy in direction:
            nx, ny = xp + dx, yp + dy
            if not (0 <= nx < L and 0 <= ny < L):
                continue
            if dist[nx][ny] == -1:
                queue.append((nx, ny))
                dist[nx][ny] = dist[xp][yp] + 1
    return dist[e_x][e_y]


for _ in range(T):
    L = int(input().strip())

    s_x, s_y = map(int, input().split())
    e_x, e_y = map(int, input().split())

    dist = [[-1] * L for _ in range(L)]
    dist[s_x][s_y] = 0
    print(bfs(s_x, s_y, e_x, e_y, dist))