[백준] 16948번 데스 나이트 Javascript(NodeJs)

문제 링크

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

알고리즘: BFS

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.

크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.

데스 나이트는 체스판 밖으로 벗어날 수 없다.

풀이

간단한 BFS 문제임. 현재 좌표 (r1,c1)에서 이동할 수 있는 모든 좌표를 Queue에 넣고 제일 먼저 도착한 value의 cout를 출력하면 된다.
Queue에 모든 값이 pop_left 되었는데 (r2, c2)에 도착하지 못했다면 이동할 수 없는 경우이기 때문에 -1을 출력한다.

소스코드

class Queue {
    constructor() {
        this.storage = {};
        this.front = 0;
        this.rear = -1;
    }
    
    size() {
        if(this.front > this.rear) {
            return 0;
        } else {
            return this.rear - this.front + 1;
        }
    }
    
    push(value) {
        this.rear += 1;
        this.storage[this.rear] = value;
    }
    
    pop_left() {
        let value = this.storage[this.front];
        if(this.size()) {
            delete this.storage[this.front];
            this.front += 1;
        }
        return value;
    }
}
const fs = require('fs');
let inputData = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
let N = inputData[0].trim() * 1;
let input2 = inputData[1].split(' ').map(x=>x*1);
let r1 = input2[0];
let c1 = input2[1];
let r2 = input2[2];
let c2 = input2[3]
let visited = Array.from(Array(N), () => Array(N).fill(false));
console.log(BFS());

function BFS() {
    let que = new Queue();
    que.push([r1,c1, 0]);
    visited[c1][r1] = true;
    let wx = [-2, -2, 0, 0, 2, 2];
    let wy = [-1, 1, -2, 2, -1, 1];
    while(que.size()) {
        let [x, y, cout] = que.pop_left();
        if((x === r2) && (y === c2)) {
            return cout;
        }
        for(let i=0; i<6; i++) {
            let nx = x + wx[i];
            let ny = y + wy[i];
            if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
                if(!visited[ny][nx]) {
                    visited[ny][nx] = true;
                    que.push([nx, ny, cout + 1]);
                }
            }
        }
    }
    return -1;
}