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

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

7562번: 나이트의 이동

 

문제

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

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

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

 

풀이

해당 문제는 간선의 비용이 동일한 상황에서 최단 거리를 구하는 문제로 BFS 알고리즘을 사용하면 해결할 수 있는 문제이다.

1. 좌표 방문여부를 확인하기 위해 l x l 크기의 그래프를 생성한다.

2. 나이트의 한번에 이동할 수 있는 범위는 8개의 방향으로 정해져 있으므로 각 이동 방향을 x 좌표 별 배열, y좌표 별 배열로 생성한다.

3. 큐를 생성하고 현재 위치를 넣어준다.

4. 큐의 길이가 0일때 까지 반복하되 현재 위치 값이 목표 위치와 일치할 경우 while 반복문에서 탈출한다.

5. 현재위치에서 이동할 수 있는 8개의 방향 값이 범위를 벗어나면 continue로 넘어가고 방문하지 않은 경우 다음위치로 큐에 넣어주기전에 이동 횟수 +1 씩 더해주며 이동한다.

 

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

class Queue {
    constructor() {
      this.headIndex = 0;
      this.tailIndex = 0;
      this.items = {};
    }
    enqueue(item) {
      this.items[this.tailIndex] = item;
      this.tailIndex++;
    }
    dequeue() {
      const item = this.items[this.headIndex];
      delete this.items[this.headIndex];
      this.headIndex++;
      return item;
    }
    peek() {
      return this.items[this.headIndex];
    }
    getLength() {
      return this.tailIndex - this.headIndex;
    }
  }

// 이동할여덟가지방향정의
const dx = [-2, -2, -1, -1, 1, 1, 2, 2];
const dy = [1, -1, 2, -2, 2, -2, 1, -1];

// 테스트케이스의수
let caseCnt = Number(input[0]);
let line = 1;

while (caseCnt--) {
  const l = Number(input[line]);
  //방문정보
  let visited = [];
  for (let i = 0; i < l; i++) visited[i] = new Array(l).fill(0);
  
  //현재위치
  const [x, y] = input[line + 1].split(' ').map(Number);
  //목표위치
  const [targetX, targetY] = input[line + 2].split(' ').map(Number);
  
  //너비우선탐색 수행
  queue = new Queue();
  queue.enqueue([x, y]);
  visited[x][y] = 1;
  let result;
  while (queue.getLength() != 0) {
    let cur = queue.dequeue();
    //목표위치 도달시 탈출 
    if (cur[0] == targetX && cur[1] == targetY) {
      result = visited[cur[0]][cur[1]] - 1;
      break;
    }
    for (let i = 0; i < 8; i++) {
      //현재위치에서 이동하고자하는 위치 확인
      let nx = cur[0] + dx[i];
      let ny = cur[1] + dy[i];
      // 공간을 벗어난 경우 무시
      if (nx < 0 || nx >= l || ny < 0 || ny >= l) continue;
      if (visited[nx][ny] == 0) {
        // 방문하지 않은 위치인 경우
        visited[nx][ny] = visited[cur[0]][cur[1]] + 1;
        queue.enqueue([nx, ny]);
      }
    }
  }
  // 다음 테스트 케이스로 이동
  line += 3;
  console.log(result);
}