[백준] 7562 나이트의 이동 - javascript

📌 문제

https://www.acmicpc.net/problem/7562

📌 풀이

let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

let tc = Number(input[0]);
let index = 1;

for (let i = 0; i < tc; i++) {
  let board_size = Number(input[index]);
  let board = new Array(board_size);
  for (let j = 0; j < board.length; j++) {
    board[j] = new Array(board_size).fill(0);
  }
  let start_x = Number(input[index + 1].split(" ")[0]);
  let start_y = Number(input[index + 1].split(" ")[1]);
  let end_x = Number(input[index + 2].split(" ")[0]);
  let end_y = Number(input[index + 2].split(" ")[1]);
  board[start_x][start_y] = 1;
  function BFS() {
    let L = 0;
    let dx = [2, 2, -2, -2, 1, 1, -1, -1];
    let dy = [1, -1, 1, -1, 2, -2, 2, -2];
    let queue = [];
    queue.push([start_x, start_y]);
    while (queue.length) {
      let len = queue.length;
      for (let i = 0; i < len; i++) {
        let v = queue.shift();
        if (v[0] === end_x && v[1] === end_y) {
          return L;
        }
        for (let i = 0; i < 8; i++) {
          let nx = v[0] + dx[i];
          let ny = v[1] + dy[i];
          if (
            nx >= 0 &&
            nx < board_size &&
            ny >= 0 &&
            ny < board_size &&
            board[nx][ny] === 0
          ) {
            board[nx][ny] = 1;
            queue.push([nx, ny]);
          }
        }
      }
      L++;
    }
  }
  console.log(BFS());
  index += 3;
}

✔ 알고리즘 : BFS

✔ 나이트가 이동할 수 있는 방향은 8가지이므로 dx,dy에 8개값을 넣는다

✔ input으로부터 받은 start_x,start_y값을 큐에 집어넣으면서 BFS탐색 시작

✔ board[a][b]가 1인경우는 탐색중인 현재 a,b좌표는 탐색완료상태 라는 뜻

✔ board의 범위를 벗어나지 않고 board[nx][ny]가 0인 경우만 탐색 -> 방문처리 해주고 queue에 push

✔ L을 통해 이동횟수 count하고 queue에서 shift했을 때 도착지점의 좌표와 같으면 L(이동횟수) return

✔ 난이도 : 백준기준 실버2