[백준 7562] 나이트의 이동 - bfs, 너비탐색 알고리즘, javascript, node.js

문제 : 

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

7562번: 나이트의 이동

 

알고리즘 :

1. 이 문제는 전형적인 bfs 문제이다.

2. 출발지부터 하나씩 나이트를 이동시켜 최소 횟수를 출력시키면 된다.

3. 횟수를 셀때는 visit[ny][nx] = visit[y][x] + 1 로 설정해서 이동횟수를 설정해야 한다.

 

 

문제 풀이 :

1. input 에서 각각의 테스트 별로 n, 현재 위치, 목표 위치를 저장한다.

for (let i=0;i<test*3;i++){
  const n = input[1+i]*1
  let visit = Array.from({length:n},()=>Array.from({length:n},()=>0))
  let cur = input[2+i].split(' ').map(Number)
  const target = input[3+i].split(' ').map(Number)
  i+=2
  // visit[cur[0]][cur[1]] = 1;
  let queue = [cur]
  // console.log(queue)
}

 

2. 출발지부터 bfs를 시작한다.

while(queue.length){
    const [y,x] = queue.shift()
    if (y===target[0]&&x===target[1]) {
      answer.push(visit[y][x]);break;
    }
    const dy = [-2,-2,-1,-1,1,1,2,2]
    const dx = [-1,1,-2,2,-2,2,-1,1]

    for(let j=0;j<8;j++){
      const ny = y+dy[j]
      const nx = x+dx[j]
      if (ny>=0&&nx>=0&&ny<n&&nx<n&&!visit[ny][nx]){
        queue.push([ny,nx]);
        // console.log(i)
        // console.log(queue)
        visit[ny][nx]=visit[y][x]+1
      }
    }
  }

이때, 나이트의 움직임은 아래 사진과 같다.

 

3. 전체 코드

const fs = require('fs');
const path = require('path');
const filePath = process.platform === 'linux' ? '/dev/stdin' : path.join(__dirname, '/나이트.txt');
const input = fs.readFileSync(filePath).toString().trim().split('\n');


let answer = []
const test = input[0]*1

for (let i=0;i<test*3;i++){
  const n = input[1+i]*1
  let visit = Array.from({length:n},()=>Array.from({length:n},()=>0))
  let cur = input[2+i].split(' ').map(Number)
  const target = input[3+i].split(' ').map(Number)
  i+=2
  // visit[cur[0]][cur[1]] = 1;
  let queue = [cur]
  // console.log(queue)
  while(queue.length){
    const [y,x] = queue.shift()
    if (y===target[0]&&x===target[1]) {
      answer.push(visit[y][x]);break;
    }
    const dy = [-2,-2,-1,-1,1,1,2,2]
    const dx = [-1,1,-2,2,-2,2,-1,1]

    for(let j=0;j<8;j++){
      const ny = y+dy[j]
      const nx = x+dx[j]
      if (ny>=0&&nx>=0&&ny<n&&nx<n&&!visit[ny][nx]){
        queue.push([ny,nx]);
        // console.log(i)
        // console.log(queue)
        visit[ny][nx]=visit[y][x]+1
      }
    }
  }
}
console.log(answer.join('\n'))