[Javascript][BOJ] 1697 숨바꼭질

www.acmicpc.net/problem/1697

1697번: 숨바꼭질

핵심 아이디어

bfs를 사용하는 문제이다.

기존 NxN 보드에서 사용하는 것과 달린 일직선에서 적용한다는 점만 다르며, +1, -1, *2 되는 지점을 큐에 넣어서 탐색하면된다.

 

"use strict";

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const dp = Array.from({ length: 100001 }, () => Infinity);
const visited = Array.from({ length: 100001 }, () => 0);

const solution = function (input) {
    const [n, k] = input
    .shift()
    .split(" ")
    .map((e) => parseInt(e));
    
    const q = [n];
    dp[n] = 0;
    visited[n] = 1;

    while(q.length > 0){
        const curr = q.shift();
        if(curr+1 < 1000001){
            if(dp[curr+1] > dp[curr]+1 && !visited[curr+1]){
                dp[curr+1] = dp[curr]+1;
                q.push(curr+1);
                visited[curr+1] = 1;
            }
        }
        if(curr-1 >= 0){
            if(dp[curr-1] > dp[curr]+1 && !visited[curr-1]){
                dp[curr-1] = dp[curr]+1;
                q.push(curr-1);
                visited[curr-1] = 1;
            }
        }
        if(curr*2 < 1000001 && !visited[curr*2]){
            if(dp[curr*2] > dp[curr]+1){
                dp[curr*2] = dp[curr]+1;
                q.push(curr*2);
                visited[curr*2] = 1;
            }
        }
        // console.log(q);
    }
    console.log(dp[k]);

};

const input = [];
rl.on("line", function (line) {
  input.push(line);
}).on("close", function () {
  solution(input);
  process.exit();
});