[백준] 7562 나이트의 이동 Node.js (BFS 풀이)

문제

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

입력

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

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

출력

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

예제 입력 1

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

예제 출력 1

5
28
0

---

문제풀이

✅ 답안 : BFS - Queue 풀이

const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((v) => v.split(' ').map(Number));

// 나이트가 이동할 수 있는 x, y좌표 여덟 곳
const dir = [[1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1], [-2, 1], [-1, 2]];
let start, goal, N, visited; // 시작 지점, 목표 지점, 체스판 한 변의 길이, 방문 체크할 배열

const bfs = () => {
  // 시작 지점의 x,y좌표와 이동 횟수를 카운트할 초기값 0을 큐에 담는다.
  const queue = [[start[0], start[1], 0]];
  while (queue.length) {
    const [cx, cy, move] = queue.shift();

	// 현재 위치가 목적지 좌표와 같아지면 이동한 칸 수 반환
    if (cx == goal[0] && cy == goal[1]) return move;

	// 현재 위치 기준으로 나이트가 이동할 수 있는 여덟 곳 탐색할 반복문
    for (let i = 0; i < 8; i++) {
      const nx = cx + dir[i][0];
      const ny = cy + dir[i][1];

	  // 해당 위치가 체스판을 벗어나지 않았고 방문하지 않았다면
      if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny]) {
        visited[nx][ny] = true; // 방문 처리
        queue.push([nx, ny, move + 1]); // 큐에 해당 위치, 이동 횟수 +1하여 담기
      }
    }
  }
};

// 테스트케이스 입력값 정제 작업
for (let idx = 1; idx < input.length - 1; idx++) {
  N = +input[idx];
  start = input[idx + 1];
  goal = input[idx + 2];
  idx += 2;
  visited = Array.from(Array(N), () => Array(N).fill(false));

  console.log(bfs());
}