[백준 알고리즘] Node.js 7562. 나이트의 이동

1. 문제

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

7562번: 나이트의 이동

 

2. 풀이

1) 각 테스트 케이스마다 체스판의 한 변의 길이, 현재 있는 칸, 도착 지점이 나온다.

2) 최단 거리를 구하는 문제이기에 BFS를 사용한다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +inputs[0]; // 테스트 케이스
let idx = 1;
let result = "";

const bfs = (w, k, t) => {
  const visited = Array.from({length : w}, () => new Array(w).fill(0));
  visited[k[0]][k[1]] = 1;

  const queue = [];
  queue.push(k);

  // 나이트가 이동할 수 있는 경로들.
  const dx = [-2,-2,-1,-1, 2, 2, 1, 1];
  const dy = [-1, 1,-2, 2,-1, 1,-2, 2];

  while(queue.length > 0) {
    const [x, y] = queue.shift();
    
    if(x === t[0] && y === t[1]) {
      result += `${visited[x][y] - 1}\n`; // 최초 방문했을 때를 1로 설정했기 때문에 1을 빼줌.
      break;
    }

    for(let i = 0; i < 8; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

	  // 나이트가 이동한 위치가 범위 밖이라면 돌아간다.
      if(nx < 0 || nx >= w || ny < 0 || ny >= w) continue;

	  // 나이트가 방문한 적이 없다면
      if(!visited[nx][ny]) {
        visited[nx][ny] = visited[x][y] + 1;
        queue.push([nx, ny]);
      }
    }
  }
}


for (let i = 0; i < N; i++) {
  const I = +inputs[idx++];
  const knight = inputs[idx++].split(" ").map((v) => +v);
  const target = inputs[idx++].split(" ").map((v) => +v);
  
  bfs(I, knight, target);
}

console.log(result)

 

3. 정리

- 처음 나이트의 이동 경로를 잘못 작성해서 틀렸었다. 꼼꼼하게 작성하도록 해야겠다.