문제

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

큐브러버는 현재좌표 (r,c)에서 (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)
경로로 움직일 수 있는 기존의 나이트와는 다른 데스나이트를 만들었다.
데스나이트가 (r1, c1)에서 (r2, c2)로 이동할 수 있는 최소 이동횟수를 구하자

문제 접근

문제에 이동하는 최소 이동 횟수를 구해보자. 라고 적혀있다. 즉, bfs로 탐색하는 문제다.
평범하게 bfs를 적용하면 쉽게 풀리는 문제이다.

제일 처음에는 제일 짧은 경로를 탐색하기 위해 우선순위 큐를 적용했다.

근데 그럴필요가 없다는걸 문제를 풀고서 깨닫게 되었는데,
bfs에서 우선순위 큐는 노드간 간선의 가중치가 모두 다를때만 적용하면 된다.
가중치가 다를때 인접 노드중 가중치가 가장 짧은 노드를 골라야 짧은 시간안에 짧은거리를 구할 수 있기 때문이다.

정답 코드

const stdin = require('fs').readFileSync(0, 'utf-8').trim().split('\n');
const input = (() => {
  let line = 0;
  return () => stdin[line++].split(' ').map(v => +v);
})();

const solution = () => {
  const N = +input();
  const [sy, sx, ey, ex] = input();
  const movedCnt = Array.from({ length: N }, () => Array.from({ length: N }, () => Infinity));
  // (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)
  const nextMove = [
    // y,x
    [-2, -1],
    [-2, 1],
    [0, -2],
    [0, 2],
    [2, -1],
    [2, 1],
  ];
  const q = []; //new MinHeap();

  const canMove = (y, x) => {
    if (y >= 0 && y < N && x >= 0 && x < N) return true;
    return false;
  };

  // [y, x, dist, moved]
  q.push([sy, sx, ey + ex, 0]);
  while (q.length > 0) {
    const [y, x, dist, moved] = q.shift(); //q.pop();

    if (dist === 0) return moved;

    for (const [ny, nx] of nextMove) {
      const [py, px] = [ny + y, nx + x];
      if (!canMove(py, px)) continue;
      if (movedCnt[py][px] <= moved + 1) continue;

      const nextDist = Math.abs(px - ex) + Math.abs(py - ey);
      movedCnt[py][px] = moved + 1;
      q.push([py, px, nextDist, moved + 1]);
    }
  }
  return -1;
};

console.log(solution());