[백준] 13549번 - 숨바꼭질 3 Javascript(NodeJs)

문제 링크

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

풀이

알고리즘: 0-1 BFS

1.0-1 BFS 풀이

class Deque {
    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_back(value) {
        this.rear += 1;
        this.storage[this.rear] = value;
    }
    
    push_front(value) {
        this.front -= 1;
        this.storage[this.front] = 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 [N, K] = fs.readFileSync('/dev/stdin').toString().trim().split(' ').map(x=>x*1);
let visited = new Array(100001).fill(-1);
BFS();
console.log(visited[K]);

function BFS() {
    let deque = new Deque();
    deque.push_back([N, 0]);
    while(deque.size() !== 0) {
        if(visited[K] !== -1) {
            return;
        }
        let [n, value] = deque.pop_left();
        visited[n] = value;
        let nx = [n*2, n+1, n-1];
        for(let i=0; i<nx.length; i++) {
            if(nx[i] >= 0 && nx[i] <= 100000) {
                if(visited[nx[i]] === -1) {
                    if(i===0) {
                        //우선 순위가 더 높음.
                        deque.push_front([nx[i], visited[n]]);
                    } else {
                        deque.push_back([nx[i], visited[n]+1]);
                    }
                }
            }
        }
    }
}