[백준 7562 - Node.js] 나이트의 이동

🔗 문제 링크

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

7562번: 나이트의 이동

✏️ 풀이

const offset = [
  [-1, -2], [-2, -1], [-2, 1], [-1, 2],
  [1, 2], [2, 1], [2, -1], [1, -2]
];

const bfs = (start, [ex, ey], l, visited) => {
  const queue = [start];
  while (queue.length) {
    const [x, y, depth] = queue.shift();
    if (x === ex && y === ey) {
      return depth;
    }
    for (let i = 0; i < 8; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < l && ny >= 0 && ny < l && !visited[nx][ny]) {
        visited[nx][ny] = true;
        queue.push([nx, ny, depth + 1]);
      }
    }
  }
}

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");
for (let i = 0; i < +input[0]; i++) {
  const l = +input[i * 3 + 1];
  const [sx, sy] = input[i * 3 + 2].split(' ').map(v => +v);
  const [ex, ey] = input[i * 3 + 3].split(' ').map(v => +v);
  const visited = [...Array(l)].map(() => Array(l).fill(false));
  visited[sx][sy] = true;
  console.log(bfs([sx, sy, 0], [ex, ey], l, visited));
}

테스트 케이스별로 체스판의 크기, 시작점, 도착점의 정보를 가지고 BFS를 실행하여 도착점에 도달하는 최단거리를 구하면 된다.

 

BFS를 실행할 때 queue에 [x, y, depth]의 형태로 자료를 넣고, 나이트의 8가지 이동 방향에 대하여 유효성 검사 및 방문 여부를 체크한 뒤 queue에 depth를 1 증가한 상태로 push한다. 탐색을 계속 하다가 도착점과 동일한 좌표일 경우에 즉시 depth를 반환하도록 하였다.

 

 

💡 새로 알게 된 점

const bfs = (start, [ex, ey], l, visited) => {
  const queue = [start];
  while (queue.length) {
    const [x, y, depth] = queue.shift();
    if (x === ex && y === ey) {
      return depth;
    }
    if (!visited[x][y]) {
        visited[x][y] = true;
        for (let i = 0; i < 8; i++) {
        const nx = x + offset[i][0];
        const ny = y + offset[i][1];
        if (nx >= 0 && nx < l && ny >= 0 && ny < l) {
          queue.push([nx, ny, depth + 1]);
        }
      }
    }
  }
}

원래 항상 BFS 문제를 풀 때 이러한 형식으로 queue에서 shift한 후에 좌표의 방문 여부를 따졌었는데, 이렇게 하면 나이트의 8방향 이동에 대해서 queue에 push할 때 방문 여부를 체크하지 않아서 일단 유효성 검사만 통과하면 queue에 push가 되어 불필요하게 queue의 shift 연산 횟수가 증가하였다. 안 그래도 queue를 직접 구현하지 않고 배열의 shift를 쓰면 시간복잡도가 O(n)이라 오래 걸리는데, 그 횟수마저 커지게 되었던 것이다. 그래서 위 코드는 시간 초과가 났다.

 

const bfs = (start, [ex, ey], l, visited) => {
  const queue = [start];
  while (queue.length) {
    const [x, y, depth] = queue.shift();
    if (x === ex && y === ey) {
      return depth;
    }
    for (let i = 0; i < 8; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < l && ny >= 0 && ny < l && !visited[nx][ny]) {
        visited[nx][ny] = true;
        queue.push([nx, ny, depth + 1]);
      }
    }
  }
}

// ...생략...

for (let i = 0; i < +input[0]; i++) {
  // ...생략...
  visited[sx][sy] = true;
  console.log(bfs([sx, sy, 0], [ex, ey], l, visited));
}

그래서 위와 같이 방문 여부 검사를 queue에 push하기 전에 해주도록 변경하여 통과하였다.

그리고 맨 첫 번째 좌표는 BFS를 하기 전에 따로 방문 여부를 갱신해주었다. (visited[sx][sy] = true)