백준 14395 JS 풀이

구하는 값

4칙연산으로 최소연산횟수구하기

핵심 아이디어

최소연산횟수 → bfs

que안에 넣을 때 연산자들을 같이 넣어줌

코드

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

class Queue {
    constructor() {
        this.q = [];
        this.h = 0;
        this.t = 0;
    }
    enque(v) {
        this.q[this.t++] = v;
    }

    deque() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }

    size() {
        return this.t - this.h;
    }
}

const [s, t] = input[0].split(" ").map(Number);

// const visited = new Array(t + 1).fill("");

const visited = [];
let ans = -1;
function bfs() {
    const queue = new Queue();
    queue.enque([s, ""]);
    visited.push(s);

    while (queue.size()) {
        const [cur, str] = queue.deque();
        if (cur === t) {
            ans = str;
            break;
        }

        if (!visited.includes(cur ** 2)) {
            queue.enque([cur ** 2, str + "*"]);
            visited.push(cur ** 2);
        }

        if (!visited.includes(cur * 2)) {
            queue.enque([cur * 2, str + "+"]);
            visited.push(cur * 2);
        }

        if (!visited.includes(0)) {
            queue.enque([0, str + "-"]);
            visited.push(0);
        }

        if (!visited.includes(1)) {
            queue.enque([1, str + "/"]);
            visited.push(1);
        }
    }
}
bfs();

if (s === t) ans = 0;

console.log(ans);