[baekjoon] #7562 나이트의 이동 (Node.js)

📖 문제

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

☃️ 풀이

처음에는 DFS로 시도 했다가 계속 Maximum Call Stack 에러가 발생했다. 사방이 아닌 팔방을 탐색해야 했기 때문에 재귀를 너무 깊게 탐색하는 것이 원인이라고 판단했다.

그래서 BFS로 시도했다. 사실 알고리즘 자체는 크게 어려운 편이 아니다. 흔히 아는 상하좌우 그래프 탐색에서 탐색 위치만 변경해주면 된다.

const dxs = [-2, -1, 1, 2, 2, 1, -1, -2]
const dys = [1, 2, 2, 1, -1, -2, -2, -1]

나머지는 일반적인 BFS와 동일하게 방문한 적 없는 좌표값을 queue에 넣으며 해당 방향으로 탐색해나간다.

이 때 현재 좌표와 함께 나이트가 몇 번 이동했는지에 대한 count 값을 함께 넘겨준다. 이제 현재 좌표와 목적지 좌표가 같을 때 cnt를 출력하면 된다.

💽 소스코드

const input = require('fs').readFileSync('input.txt').toString().split('\n');
const m = Number(input.shift());

const dxs = [-2, -1, 1, 2, 2, 1, -1, -2];
const dys = [1, 2, 2, 1, -1, -2, -2, -1];

for (let i = 0; i < m; i++) {
  const n = Number(input.shift());
  const [cx, cy] = input.shift().split(' ').map(Number);
  const [gx, gy] = input.shift().split(' ').map(Number);
  const visited = Array.from({ length: n }, () =>
    Array.from({ length: n }, () => 0)
  );

  visited[cy][cx] = 1;
  console.log(search([cx, cy, 0], [gx, gy], n, visited));
}

function in_range(x, y, n) {
  return 0 <= x && x < n && 0 <= y && y < n;
}

function search(cur, [gx, gy], n, visited) {
  const queue = [cur];

  while (queue.length > 0) {
    let [x, y, cnt] = queue.shift();

    if (x === gx && y === gy) return cnt;

    for (let i = 0; i < 8; i++) {
      let nx = x + dxs[i];
      let ny = y + dys[i];

      if (in_range(nx, ny, n) && !visited[ny][nx]) {
        queue.push([nx, ny, cnt + 1]);
        visited[ny][nx] = 1;
      }
    }
  }
}