백준 1697 JS풀이

구하는 값

-1, 1, *2 를 통해 원하는 곳까지 갈 수있는 '최단거리'

핵심 아이디어

visited를 루트로부터 거리로 하여 BFS

구현방법

먼저 BFS를 구현하기 위해 Queue clss를 만들어주고
루트값을 queue에 넣고 queue가 빌때까지 while문을 돌면서 dequeue해주고 다음 노드가 방문한적 없는 노드라면 queue에 enqueue를 반복하며 현재 노드가 k 가 되었을 때 종료

코드

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());