[백준] 7562번 나이트의 이동 - JavaScript(NodeJS)

문제

7562번: 나이트의 이동

 

풀이

I x I 행렬에서, 나이트의 위치에서 목표 위치까지 얼마나 빨리 갈 수 있는지를 구하는 문제이다.
최단경로를 구하면 되므로 BFS를 사용해보자.

나이트가 이동 가능한 위치

 

나이트가 이동 가능한 위치는 그림과 같다.

 

나이트가 동일한 위치를 두 번 방문하는 것은 다른 위치로 이동했다가 다시 돌아온 경우이므로,
이를 방지하기 위해 visit 행렬을 통해서 이전 위치로 되돌아가는 경우를 배제한다.

 

나이트는 총 8방향으로 이동할 수 있으므로, 나이트의 현재 위치를 기준으로 8개 방향의 이동 가능성을 조회하면 된다.

 

const sol = (input) => {
  const N = +input[0];
  let idx = 1; // 입력 처리를 위해 input의 인덱스를 조회하는 변수.
  let result = "";

  function bfs(knight, target, I) {
    const queue = [];
    queue.push(knight);
    const visit = Array.from({ length: I }, () => Array(I).fill(0));
    visit[knight[0]][knight[1]]=1;
    const dx = [-2, -1, 1, 2, 2, 1, -1, -2]; // dx, dy는 나이트가 이동 가능한 좌표.
    const dy = [1, 2, 2, 1, -1, -2, -2, -1];
    while (queue.length) {
      const [x, y] = queue.shift();
      if (x === target[0] && y === target[1]) { // (x,y) 좌표 값이 target에 도달했으면 즉시 종료.
        result += `${visit[x][y] - 1}\n`; // 시작 위치 값을 0이 아닌 1로 설정했으므로, 최종 도착 값에서 1을 빼준다.
        break;
      }
      for (let i = 0; i < 8; i++) {
        const [nx, ny] = [x + dx[i], y + dy[i]];
        if (nx < 0 || ny < 0 || nx >= I || ny >= I) continue;
        if (!visit[nx][ny]) { // 만약 이미 방문을 한 위치라면 조회하지 않는다.
          visit[nx][ny] = visit[x][y] + 1; // visit[x][y]는 (x,y)까지의 최단경로이므로, 1을 더해주면 (nx,ny)까지의 최단경로.
          queue.push([nx, ny]);
        }
      }
    }
  }

  for (let i = 0; i < N; i++) { // N개 테스트 케이스를 순차적으로 테스트한다.
    const I = +input[idx++];
    const knight = input[idx++].split(" ").map((v) => +v);
    const target = input[idx++].split(" ").map((v) => +v);
    bfs(knight, target, I);
  }
  return result;
};

// 백준에서 입력을 받는 코드
const input = [];
require("readline")
  .createInterface(process.stdin, process.stdout)
  .on("line", (line) => {
    input.push(line);
  })
  .on("close", () => {
    console.log(sol(input));
    process.exit();
  });