백준 1697 JS 풀이

구하는 값

동생을 찾는 가장 빠른 방법

핵심 아이디어

수빈위치부터 동생까지 bfs

아래방법은 array로 방문처리를했지만 set으로 하는게 더 간편해보임

코드

class Queue {
    constructor() {
        this.que = [];
        this.head = 0;
        this.tail = 0;
    }

    enque(v) {
        this.que[this.tail++] = v;
    }

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

    size() {
        return this.tail - this.head;
    }
}

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

const [n, k] = input[0].split(" ").map(Number);

const max = 100001;
const visited = new Array(max).fill(0);
const queue = new Queue();

function bfs() {
    queue.enque(n);

    while (queue.size()) {
        const cur = queue.deque();
        if (cur === k) return visited[cur];

        for (const next of [cur - 1, cur + 1, cur * 2]) {
            if (next < 0 || next >= max) continue;
            if (!visited[next]) {
                visited[next] = visited[cur] + 1;
                queue.enque(next);
            }
        }
    }
}

console.log(bfs());