나이트의 이동

나이트의 이동

문제 설명

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

📥 예제 입력

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

📤 예제 출력

5
28
0

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : path.join(__dirname, "input.txt"))
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  let idx = 0;
  const T = input[idx++];
  const dx = [-2, -1, 1, 2, 2, 1, -1, -2];
  const dy = [1, 2, 2, 1, -1, -2, -2, -1];
  const results = [];

  for (let tc = 0; tc < T; tc++) {
    const N = Number(input[idx++]); // 체스판 한 변 길이
    const [startX, startY] = input[idx++].split(" ").map(Number);
    const [endX, endY] = input[idx++].split(" ").map(Number);
    const visited = Array.from({ length: N }, () => Array(N).fill(false));

    const bfs = () => {
      let queue = [[startX, startY, 0]];

      visited[startX][startY] = true;

      let head = 0;
      while (queue.length > head) {
        const [x, y, cnt] = queue[head++];

        if (x === endX && y === endY) return cnt;

        for (let k = 0; k < 8; k++) {
          let nx = x + dx[k];
          let ny = y + dy[k];

          if (0 <= nx && nx < N && 0 <= ny && ny < N && !visited[nx][ny]) {
            visited[nx][ny] = true;
            queue.push([nx, ny, cnt + 1]);
          }
        }
      }
    };
    results.push(bfs());
  }
  console.log(results.join("\n"));
};
solution(input);

아이디어 / 접근법

1. 시작 좌표에서 끝 좌표까지 계속 이동하면서 카운트 누적
2. 나이트의 이동 경로에 따른 델타 배열 선언
3. BFS 돌리면서 카운트 누적
4. 끝

후기

마지막 값이 -2 가 되었어야 하는데 이 부분을 좀 몰라서 자꾸 틀렸다.. 문제 좀 잘 보자...