문제

https://www.acmicpc.net/problem/1600
원숭이가 말처럼 움직이고싶다 !
하지만 K번만 말처럼 움직이고 나머진 원숭이처럼 움직여야 한다!
이때 좌상단에서 우하단으로 가능방법중 가장 짧은길은?

여기서 말은 체스판의 말처럼 움직인다.

풀이

예전에 풀었던 문제중 https://www.acmicpc.net/problem/2206 와 비슷하다.
사실 비슷한게 아니라 거의 같은 문제이다.

해당 문제는 visited를 2개 써서 풀이하는 문제였다.
벽을 부쉈을 경우의 visited, 벽을 안부쉈을 경우의 visited 이런식으로 나눠 풀면된다.
만약 visited 배열을 한개만 사용한다면 벽을 부수고서 다시 왔던길은 못가기 때문에
그게 최단거리인지 아닌지 알 수 없기 때문이었다.

이 문제는 K번만큼 말처럼 움직일 수 있는 문제다.
그러므로 visited 배열을 K개 만들어준 다음 말처럼, 원숭이처럼 이동할 수 있다면 이동하고
우하단에 도착하면 루프를 탈출해 정답을 출력한다.

만약 도중에 루프에서 빠져나가지 않고 큐가 비어버리면 방법이 없는것이므로 -1도 출력해준다.

정답코드

class Q {
  l = 0;
  r = 0;
  q = {};
  isEmpty = () => this.l === this.r;
  push(d) {
    this.q[this.r++] = d;
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const r = this.q[this.l];
    delete this.q[this.l++];
    return r;
  }
}
//const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
//prettier-ignore
const stdin = `
2
5 2
0 0 1 1 0
0 0 1 1 0
`.trim().split('\n');
//prettier-ignore
const input = (() => { let l = 0; return () => stdin[l++].split(' ').map(Number);})();

const K = +input();
const [W, H] = input();
const board = Array.from({ length: H }, () => input());
const visited = Array.from({ length: H }, () =>
  Array.from({ length: W }, () => Array.from({ length: K }, () => false)),
);

const moveHorse = [
  [-2, 1],
  [-2, -1],
  [-1, 2],
  [-1, -2],
  [1, 2],
  [1, -2],
  [2, 1],
  [2, -1],
];
const moveMonkey = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];
const canGo = (y, x) => y >= 0 && y < H && x >= 0 && x < W && board[y][x] !== 1;

const queue = new Q();
queue.push([0, 0, 0, 0]);

while (!queue.isEmpty()) {
  const [y, x, k, m] = queue.pop();

  if (y === H - 1 && x === W - 1) {
    console.log(m);
    return;
  }
  // 말처럼 가보는 경우
  for (const [yy, xx] of moveHorse) {
    const [ny, nx] = [y + yy, x + xx];
    if (!canGo(ny, nx)) continue;
    if (k + 1 > K) continue;
    if (visited[ny][nx][k + 1]) continue;

    queue.push([ny, nx, k + 1, m + 1]);
    visited[ny][nx][k + 1] = true;
  }
  // 원숭이처럼 가보는 경우
  for (const [yy, xx] of moveMonkey) {
    const [ny, nx] = [y + yy, x + xx];
    if (!canGo(ny, nx)) continue;
    if (visited[ny][nx][k]) continue;

    queue.push([ny, nx, k, m + 1]);
    visited[ny][nx][k] = true;
  }
}
console.log(-1);