[백준] 7562

나이트의 이동

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

풀이

class Node {
  constructor(data, prev = null, next = null) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  enQueue(data) {
    let node = new Node(data);
    node.next = this.tail;
    node.prev = this.tail.prev;
    this.tail.prev.next = node;
    this.tail.prev = node;
    this.size++;
  }
  deQueue() {
    if (this.ifEmpty()) return -1;
    let tmp = this.head.next;
    this.head.next = tmp.next;
    tmp.next.prev = this.head;
    this.size--;
    return tmp.data;
  }
  ifEmpty() {
    return this.size ? false : true;
  }
}

const knight = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\\n")
    .map((n) => n.split(" ").map(Number));
  input.shift();
  let i = 0;
  const len = input.length;
  const dir = [
    [1, 2, 2, 1, -1, -2, -2, -1],
    [-2, -1, 1, 2, 2, 1, -1, -2],
  ];
  let ans = [];
  while (i < len) {
    let size = input[i++][0];
    let arr = new Array(size);
    for (let j = 0; j < size; j++)
      arr[j] = Array.from({ length: size }, (n) => 0);
    let queue = new Queue();
    let start = input[i++];
    let end = input[i++];
    queue.enQueue(start);
    while (!queue.ifEmpty()) {
      let cur = queue.deQueue();
      if (cur[0] === end[0] && cur[1] === end[1]) {
        ans.push(arr[cur[0]][cur[1]]);
        break;
      }
      for (let j = 0; j < 8; j++) {
        let coord = [cur[0] + dir[0][j], cur[1] + dir[1][j]];
        if (
          coord[0] < 0 ||
          coord[0] >= size ||
          coord[1] < 0 ||
          coord[1] >= size
        )
          continue;
        if (arr[coord[0]][coord[1]]) continue;
        arr[coord[0]][coord[1]] = arr[cur[0]][cur[1]] + 1;
        queue.enQueue([coord[0], coord[1]]);
      }
    }
  }
  console.log(ans.join("\\n"));
};

knight();

반성회

BFS를 사용하되 이동방향 (dir 배열) 을 나이트의 이동방향 8종류로 설정하면 된다