백준[JS] > 1697번 숨바꼭질

➕문제링크

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

🔨문제풀이

bfs를 이용하돼 불필요한 연산은 처리하지 않는 방향으로 최적화 하였다. ( dp[ i ] 는 i지점을 가는 데 걸리는 최소시간 )

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();

let [N, K] = input.split(" ").map((n) => Number(n));

let dp = Array(100001).fill(Infinity);
let endPoint = 100000;
let index = N;
let answer = undefined;
dp[N] = 0;

let queue = [[N, 0]];
while (queue.length) {
    let [point, time] = queue.shift();

    if (point === K) {
        answer = time;
        break;
    }

    if (point * 2 <= endPoint && dp[point * 2] > time + 1) {
        dp[point * 2] = time + 1;
        queue.push([point * 2, time + 1]);
    }

    if (point + 1 <= endPoint && dp[point + 1] > time + 1) {
        dp[point + 1] = time + 1;
        queue.push([point + 1, time + 1]);
    }

    if (point - 1 >= 0 && dp[point - 1] > time + 1) {
        dp[point - 1] = time + 1;
        queue.push([point - 1, time + 1]);
    }
}
console.log(answer);