[JavaScript] 백준 실버 1 : 18404 - 현명한 나이트

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

---

풀이

bfs 사용해서 이동 최단 거리 찾으면 되는 문제. 처음에는 각 위치마다 bfs를 돌려주었는데 visited를 매번 생성하거나, 초기화하는 방법 모두 메모리 초과가 발생하여 한번의 bfs로 탐색하는 방법으로 작성해주었더니 해결되었다.

일반 bfs에서 상하좌우 말고 나이트가 이동 가능한 8개의 위치를 반복문으로 돌리며 접근해주면 된다.

정답 코드 - JavaScript

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n");

const [n, m] = input.shift().split(" ").map(Number);
const [sx, sy] = input
  .shift()
  .split(" ")
  .map((v) => Number(v) - 1);
const points = input.map((str) => str.split(" ").map((v) => Number(v) - 1));

const dx = [-2, -2, -1, -1, 1, 1, 2, 2];
const dy = [-1, 1, -2, 2, -2, 2, -1, 1];

const bfs = () => {
  const visited = Array.from({ length: n }, () => Array(n).fill(false));
  const distance = Array.from({ length: n }, () => Array(n).fill(Infinity));

  const queue = [];
  queue.push([sx, sy, 0]);
  distance[sx][sy] = 0;

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

    for (let i = 0; i < dx.length; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;

      visited[nx][ny] = true;
      distance[nx][ny] = d + 1;
      queue.push([nx, ny, d + 1]);
    }
  }

  return distance;
};

const d = bfs();
const answer = points.map(([x, y]) => d[x][y]).join(" ");

console.log(answer);