백준 node.js 13913번 숨바꼭질 4 BFS JavaScript JS

13913번: 숨바꼭질 4

문제 풀이 방법

다른 언어면 잘 모르겠지만, node.js로 푸니깐 메모리초과의 환장을 보여주었습니다..

제가 생각했을 때 문제의 핵심은 다음과 같습니다

1. 메모리초과를 생각하여 Queue를 직접 구현한 BFS를 사용한다.
2. 메모리초과를 생각하여 방문한 노드를 링크드 리스트로 연결하여 답을 낼 때 까지 순회한다.

정답 코드

//Queue 구현을 위한 노드 구현
class Node{
  constructor(value){
    this.data = value;
    this.next = null;
  }
}
//Queue 구현
class Queue {
  constructor(){
    this.front = null;
    this.rear = null;
    this.length = 0;
  }
  add(value){
    const node = new Node(value)
    this.length++
    if(this.length === 1){
      this.front = node
      this.rear = node
    }else{
      this.rear.next = node
      this.rear = node;
    }
  }
  deq(){
    const returnValue = this.front.data
    this.front = this.front.next
    this.length--
    return returnValue;
  }
}

let fs = require('fs');
let [N,K] = fs.readFileSync('/dev/stdin').toString().trim().split(" ").map(Number);
//링크드 리스트를 생성할 객체 visited
//key값으로 해당 노드를 value값으로 이전 노드를 넣는다.
//예로 52:26 이라면, 52노드를 방문하기 이전 노드가 26인 셈이다.
const visited = {}

const queue = new Queue();
queue.add(N);

//BFS
while (queue.length > 0) {
  const cur = queue.deq();
  if (cur === K) {
    const history = [K];
    let num = K
    while(num !== N){
      const curNum = visited[num]
      history.push(curNum)
      num = curNum
    }
    console.log(history.length-1)
    console.log(history.reverse().join(" "))
    break;
  }
  next(cur);
}
function next(cur) {
  if (cur !== 0 && cur < K && visited[cur*2] === undefined) {
      visited[cur*2] = cur;
      queue.add(cur * 2);
  }
  if (cur !==0 && visited[cur - 1] === undefined) {
    visited[cur-1] = cur;
    queue.add(cur - 1);
  }
  if (cur <= K*2 && visited[cur + 1] === undefined) {
    visited[cur+1] = cur;
    queue.add(cur + 1);
  }
}

---

골드 문제로 넘어가면서 BFS에서 Queue구현은 너무나 당연해 지는 것 같네요!