백준7562 - 나이트의 이동 (BFS) node.js

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

해당 문제는 가로 한칸, 세로 두 칸 혹은 가로 두 칸, 세로 한 칸씩 움직이는 체스판의 '나이트'가 목적지에 도착하기 위해 몇번을 움직여야 하는지 출력하는 문제다.

 

문제 해결 방식

최소 움직임을 요구하기 때문에, BFS 알고리즘을 활용해서 접근했다.

queue 역할을 위한 배열을 선언한 뒤, (x좌표, y좌표, 거리)를 대입한 뒤 BFS 알고리즘을 통해 해결하면 되는데,

이때 나이트가 움직일 다음 위치만 신경써주면 된다.

 

전체 소스 코드

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

function solution(data) {
  data.shift();

  const result = [];
  data.forEach((_, idx) => {
    if (idx % 3 == 0) {
      const temp = data.slice(idx, idx + 3);
      result.push(BFS(temp));
    }
  });

  console.log(result.join("\n"));
}

function BFS(arr) {
  const n = +arr.shift();
  const visited = Array.from({ length: n }, () => {
    return Array.from({ length: n }, () => 0);
  });
  const [[x, y], [tx, ty]] = arr.map((el) => el.split(" ").map(Number));

  const queue = [[x, y, 1]];

  while (queue.length) {
    const [x, y, dist] = queue.shift();

    if (visited[y][x]) continue;
    if (x == tx && y == ty) return dist - 1;

    visited[y][x] = dist;

    const directions = [
      [-1, -2],
      [-1, 2],
      [1, -2],
      [1, 2],
      [-2, -1],
      [-2, 1],
      [2, -1],
      [2, 1],
    ];
    for (let i = 0; i < directions.length; i++) {
      const [dx, dy] = directions[i];
      const [nx, ny] = [dx + x, dy + y];
      if (verify(n, nx, ny) && !visited[ny][nx]) {
        queue.push([nx, ny, dist + 1]);
      }
    }
  }
}

function verify(n, x, y) {
  return 0 <= x && x < n && 0 <= y && y < n;
}

solution(input);