백준 7562 [nodejs] 나이트의 이동

const line = require("fs").readFileSync("/dev/stdin", "utf8");
let input = line.trim().split("\n");

let map = [];
let destination = [];
let result = 0;
let size = 0;
//나이트가 이동할 수 있는 경우의 수
const moves = [
  [-2, -1],
  [-2, 1],
  [2, -1],
  [2, 1],
  [-1, -2],
  [-1, 2],
  [1, -2],
  [1, 2],
];
chess();

function chess() {
  test = parseInt(input.splice(0, 1));
  for (i = 0; i < test; i++) {
    let cnt = 0;
    size = parseInt(input[i * 3]);
    current = input[i * 3 + 1].split(" ").map(Number);
    destination = input[i * 3 + 2].split(" ").map(Number);
    let queue = [];
    map = Array.from(Array(size), () => Array(size).fill(0));
    map[current[0]][current[1]] = 1;
    queue.push([current[0], current[1]]);
    bfs(queue, cnt);
    console.log(result - 1);
  }
}

function bfs(queue, cnt) {
  let visitnext = [];

  while (queue.length) {
    const [x, y] = queue.shift();

    if (x == destination[0] && y === destination[1]) {
      result = map[x][y];
      break;
    }
	//이동할 수 있는 경우의 수 모두 구하기
    for (let i of moves) {
      let nx = x + i[0];
      let ny = y + i[1];
      if (check(nx, ny) && map[nx][ny] === 0) {
        visitnext.push([nx, ny]);
        map[nx][ny] = map[x][y] + 1;
      }
    }
  }
  //경우의 수마다 갈 수 있을 때까지 반복
  if (visitnext.length) bfs(visitnext, cnt);
}

function check(x, y) {
  if (x > -1 && y > -1 && x < size && y < size) return true;
  return false;
}

 

 

 

나이트의 이동같은 경우는 자신이 원하는 위치까지 몇 번을 움직여야 갈 수 있는가를 찾는 것이기 때문에

bfs와 dfs를 섞어서 풀게 되었다.

일단 갈 수 있는 경우의 수를 다 구한 후에 그 경우의 수마다 dfs로 깊이 탐색을 하고 거기서 목적지에 다다르게 되면

반복문을 빠져나가 결과값을 낼 수 있게 하였다.

 

bfs와 dfs를 적절히 섞어서 코드를 하는 것이 중요한 포인트였던 것 같다.