[BOJ] 7562: 나이트의 이동 / JS

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

 

 

 

 

const [t, ...input] = require('fs')
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split('\n');

const dx = [-2, -2, 2, 2, -1, 1, -1, 1];
const dy = [-1, 1, -1, 1, 2, 2, -2, -2];

let l;
let map;
function mapping() {
  map = new Array(l);
  for (let i = 0; i < l; i++) map[i] = Array.from({ length: l }, () => 0);
}

function isVisit(x, y) {
  return map[x][y];
}

function isRange(x, y) {
  return x >= 0 && x < l && y >= 0 && y < l;
}

function bfs([fromX, fromY], [toX, toY]) {
  const queue = [[fromX, fromY, 0]];
  map[fromX][fromY] = 1;

  while (true) {
    const [x, y, d] = queue.shift();
    if (x === toX && y === toY) return d;
    for (let k = 0; k < 8; k++) {
      const nx = x + dx[k];
      const ny = y + dy[k];
      if (!isRange(nx, ny) || isVisit(nx, ny)) continue;
      queue.push([nx, ny, d + 1]);
      map[nx][ny] = 1;
    }
  }
}

function solution() {
  for (let i = 0; i < t; i++) {
    l = Number(input.shift());
    mapping();
    from = input.shift().split(' ').map(Number);
    to = input.shift().split(' ').map(Number);
    console.log(bfs(from, to));
  }
}
solution();

시작점을 0부터 시작해서 나이트가 이동할 수 있는 8칸에 대해 현재 이동값에 1만큼 더한 후 큐에 넣는 것을 반복하면 도착점까지의 최소 이동거리를 구할 수 있다.

 

solution 함수는 입력된 테스트케이스만큼 연산을 반복한다.

먼저 변수 l에 체스판의 한 변의 길이를 담고, mapping 함수에 전달하여 변수 map에 l * l 크기의 2차원 배열을 세팅한다.

map은 나이트가 이전에 이동했던 칸인지 확인하는 용도로 사용된다.

이제 변수 from과 to에 시작점과 도착점의 위치를 담고 bfs함수에 인자로 넘기면 나이트의 최소 이동 횟수를 구할 수 있다.

 

bfs 함수는 이전 문제들에서 작성했던 로직과 크게 다르지 않다.

나이트가 이동할 수 있는 방향이 8방향이므로 dx, dy 배열에 각 8방향에 대한 이동값을 설정해주고,

그에 맞게 큐에서 front를 pop한 후 실행하는 반복도 8번 해주면 된다.

큐에는 나이트의 위치값뿐만 아니라 지금까지 이동한 횟수를 누적해서 담아야한다. => d

이미 나이트가 한 번 도착한 칸은 1로 설정해서 다시 지나가지 않도록 한다. => map[nx][ny] = 1