[BOJ] 숨바꼭질4 | BFS -메모리 초과 해결

Problem | 숨바꼭질4

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력 |
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

입력 예제 |
5 17

입력 출력 |
4
5 10 9 18 17

✨ 접근 방식

같은 접근 방식을 적용해도 메모리 추가 문제가 떴었다 ! ! !

검사 할 배열 선언시,
let arr=new Array(100001).fill(0); 기존에 이렇게 선언했다면, let arr=new Array(100001).fill(-1); 이렇게 바꿔주니까 맞았다고 떴다.

- ✔️ 전체코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
splited=input[0].split(' ');

let N=Number(splited[0]);
let K=Number(splited[1]);
let arr=new Array(100001).fill(-1);

let answer=0;
let flag=false;
function BFS(){
  let queue=[];
  queue.push(N);
  arr[N]=1;
  while(queue.length){
    let len=queue.length;
    for(let i=0;i<len;i++){
      let x=queue.shift();
      if(x===K) {
        flag=true;
        /*flag를 통해 while문을 빠져나올 수 있게끔*/
        break;
      }
      for(let nx of [x-1,x+1,2*x]){
        if(arr[nx]===-1){
          queue.push(nx);
          arr[nx]=x;
        }
      }
    }
    if(flag) break;
    answer++;
  }
}
BFS();
let answer2=new Array();
let searchX=K;
while(searchX!==N){
  answer2.push(searchX);
  searchX=arr[searchX];
}
answer2.push(N);
/* 마지막에 answer2라는 배열에 N까지 넣어줘야 완성*/

answer2.reverse();
console.log(answer);
console.log(answer2.join(' '));

-1은 되고 .. 왜 0은 안되는대요 ...