백준 JS 1600번 말이 되고픈 원숭이 BFS

1600번: 말이 되고픈 원숭이

첫 번째 시도

BFS에 길이가 2인 배열을 만들고, knight 움직임으로 갈 수 있는지 여부를 0번째 인덱스에, 정점에 도달하는데 걸리는 최소 횟수를 1번째 인덱스에 넣어서 풀었다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const K = +input.shift();
const [W, H] = input.shift().split(" ").map(Number);
const map = input.map((v) => v.split(" ").map(Number));
const bfs = Array.from({ length: H }, () =>
  Array.from({ length: W }, () => [Infinity, Infinity])
);

const Queue = [[0, 0]];
let order = 0;
bfs[0][0] = [K, 0];
const knightNext = [
  [2, 1],
  [1, 2],
  [2, -1],
  [-1, 2],
  [-2, 1],
  [1, -2],
  [-2, -1],
  [-1, -2]
];
const nomalNext = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0]
];
while (Queue.length > order) {
  const [a, b] = Queue[order];
  const [Kcount, count] = bfs[a][b];
  if (a === H - 1 && b === W - 1) break;
  for (let [a2, b2] of knightNext) {
    if (a + a2 >= 0 && a + a2 < H && b + b2 >= 0 && b + b2 < W) {
      if (map[a + a2][b + b2] === 0) {
        if (Kcount > 0 && bfs[a + a2][b + b2][1] > count + 1) {
          bfs[a + a2][b + b2] = [Kcount - 1, count + 1];
          Queue.push([a + a2, b + b2]);
        }
      }
    }
  }
  for (let [a2, b2] of nomalNext) {
    if (a + a2 >= 0 && a + a2 < H && b + b2 >= 0 && b + b2 < W) {
      if (map[a + a2][b + b2] === 0) {
        if (bfs[a + a2][b + b2][1] > count + 1) {
          bfs[a + a2][b + b2] = [Kcount, count + 1];
          Queue.push([a + a2, b + b2]);
        }
      }
    }
  }
  order++;
}
console.log(bfs[H - 1][W - 1][1] === Infinity ? -1 : bfs[H - 1][W - 1][1]);

하지만 위 풀이는 knight 능력을 사용함과 하지 않음에 따라 최소 횟수가 달라질 수 있어 knight 횟수 별로 최소 횟수를 저장해야 한다는 것을 깨달았다.

---

두 번째 시도

이번에는 BFS에 knight 능력 사용 횟수에 따른 최소 횟수를 각각 모두 집어 넣었다.

knight 능력을 1번 사용할 수 있으면 첫 번째 인덱스에, 2번 사용할 수 있으면 두 번째 인덱스에, … K번 사용할 수 있으면 K 번째 인덱스에 넣었다.

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n");
const K = +input.shift();
const [W, H] = input.shift().split(" ").map(Number);
const map = input.map((v) => v.split(" ").map(Number));
const bfs = Array.from({ length: H }, () =>
  Array.from({ length: W }, () => Array(K+1).fill(Infinity))
);

const Queue = [[0, 0]];
let order = 0;
bfs[0][0][K] = 0;

const knightNext = [
  [2, 1],
  [1, 2],
  [2, -1],
  [-1, 2],
  [-2, 1],
  [1, -2],
  [-2, -1],
  [-1, -2]
];
const nomalNext = [
  [0, 1],
  [1, 0],
  [0, -1],
  [-1, 0]
];
while (Queue.length > order) {
  const [a, b] = Queue[order];
  const count = bfs[a][b];
  for (let [a2, b2] of knightNext) {
    if (a + a2 >= 0 && a + a2 < H && b + b2 >= 0 && b + b2 < W) {
      if (map[a + a2][b + b2] === 0) {
        for(let i=1; i<count.length; i++){
          if (bfs[a + a2][b + b2][i-1] > count[i] + 1){
            bfs[a + a2][b + b2][i-1] = count[i] + 1
            Queue.push([a + a2, b + b2]);
          }
        }
      }
    }
  }
  for (let [a2, b2] of nomalNext) {
    if (a + a2 >= 0 && a + a2 < H && b + b2 >= 0 && b + b2 < W) {
      if (map[a + a2][b + b2] === 0) {
        for(let i=0; i<count.length; i++){
          if (bfs[a + a2][b + b2][i] > count[i] + 1){
            bfs[a + a2][b + b2][i] = count[i] + 1
            Queue.push([a + a2, b + b2]);
          }
        }
      }
    }
  }
  order++;
}
console.log(
  Math.min(...bfs[H - 1][W - 1]) === Infinity ?
  -1 :
  Math.min(...bfs[H - 1][W - 1]) 
  );