백준 node.js 14442번 벽 부수고 이동하기2 BFS JavaScript JS

14442번: 벽 부수고 이동하기 2

나를 3시간 동안 괴롭힌 문제…

문제 자체는 쉬워 보였습니다. 그러나 메모리 초과와 시간 초과가 계속해서 나오고, 어디가 문제인지 가늠되지 않았기에 글을 조금 적어봅니다.

 

문제 핵심

이 문제의 핵심이라 생각되는 것은

1. DFS가 아닌 BFS로 푼다.
2. Queue를 직접 만들어야 한다.

틀린 문제풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const [N,M,K] = input.shift().split(" ").map(Number)
const next = [[0,1],[0,-1],[1,0],[-1,0]]

const data = input.splice(0,N).map(v => v.split("").map(Number))
const memo = Array.from({length:N},()=>Array.from({length:M},()=>Array(K+1).fill(Infinity)))
memo[0][0][0] = 1
const Queue = [[0,0,0]] //Queue를 만든다
let i = 0;
while(Queue.length > i){
  const [a,b,wall] = Queue[i++] //Queue의 길이가 길어져 메모리 초과를 발생시킨다.
  for(let [a2,b2] of next){
    const A = a+a2
    const B = b+b2
    if(A>=0&&A<N&&B>=0&&B<M){
      if(data[A][B] === 1){
          if(memo[A][B][wall+1] > memo[a][b][wall] + 1){
            memo[A][B][wall+1] = memo[a][b][wall] + 1
            queue.push([A,B,wall+1])
        }
      }else if(data[A][B] === 0){
          if(memo[A][B][wall] > memo[a][b][wall] + 1){
            memo[A][B][wall] = memo[a][b][wall] + 1
            queue.push([A,B,wall])
        }
      }
    }
  }
}
console.log(Math.min(...memo[N-1][M-1]) === Infinity ? -1 : Math.min(...memo[N-1][M-1]))

위 방식으로 Queue의 길이가 계속해서 길어지면서 메모리초과라는 결과가 나왔습니다.

물론 shift()를 사용하면 시간초과가 나옵니다.

틀린 문제풀이2

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const [N,M,K] = input.shift().split(" ").map(Number)
const next = [[0,1],[0,-1],[1,0],[-1,0]]

const data = input.map((v) => v.split("").map(Number));
const memo = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => Array(K + 1).fill(Infinity))
);
//Queue 구현
class Queue {
  constructor(){
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  push(value){
    this.queue[this.rear++] = value
  }
  shift(){
    const returnValue = this.queue[this.front]
    delete this.queue[this.front++]
    return returnValue
  }
  length(){
    return this.rear-this.front
  }
}
// ... 아래는 같음.

이번에는 Queue를 직접 구현하였습니다. shift는 시간 복잡도가 O(n)이고, Queue에서 사용하는 방식은 delete this.queue[this.front++] 로 delete는 시간 복잡도가 O(1)입니다. 따라서 시간 초과도 나오지 않고 메모리 초과도 발생하지 않을 것이라 생각했습니다.

하지만 결과는 시간 초과.

여기서 시간을 많이 잡아먹었습니다. 어디서 시간초과가 나오는지 감이 잡히지 않았습니다

정답 문제풀이

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim().split("\\n")
const [N,M,K] = input.shift().split(" ").map(Number)
const next = [[0,1],[0,-1],[1,0],[-1,0]]

const data = input.map((v) => v.split("").map(Number));
const memo = Array.from({ length: N }, () =>
  Array.from({ length: M }, () => Array(K + 1).fill(Infinity))
);

class Node {
  constructor(value){
    this.cur = value;
    this.next = null;
  }
}

class Queue {
  constructor(){
    this.front = null;
    this.rear =null;
    this.length = 0;
  }
  push(value){
    const node = new Node(value);
    if(this.length === 0){
      this.front = node;
    }else {
      this.rear.next = node;
    }
    this.rear = node;
    this.length++
  }
  shift(){
    if(this.length === 0) return false;
    const returnValue = this.front.cur
    this.front = this.front.next;
    this.length--;
    return returnValue;
  }
}

memo[0][0][0] = 1;
const queue = new Queue();
queue.push([0,0,0])
while(queue.length > 0){
  const [a,b,wall] = queue.shift()
  if(a === N-1 && b === M-1) break;
  for(let [a2,b2] of next){
    const A = a+a2
    const B = b+b2
    if(A>=0&&A<N&&B>=0&&B<M){
      if(data[A][B] === 1){
          if(memo[A][B][wall+1] > memo[a][b][wall] + 1){
            memo[A][B][wall+1] = memo[a][b][wall] + 1
            queue.push([A,B,wall+1])
        }
      }else if(data[A][B] === 0){
          if(memo[A][B][wall] > memo[a][b][wall] + 1){
            memo[A][B][wall] = memo[a][b][wall] + 1
            queue.push([A,B,wall])
        }
      }
    }
  }
}
console.log(
  Math.min(...memo[N - 1][M - 1]) === Infinity
    ? -1
    : Math.min(...memo[N - 1][M - 1])
);

정답인 코드의 Queue 구현은 배열이 아닌 리스트로 구현하였습니다.

사실 왜 정답인지 아직 잘 모르겠습니다.

Queue구현을 배열로 했냐, 리스트로 했냐의 차이인데, 배열로 구현했을 땐 시간초과, 리스트일 땐 정답이 나오니 어떤 문제인지 잘 모르겠네요