JavaScript / shift 안쓰고 BFS 구현하기

JS에서의 큐?

자바스크립트의 리스트는 큐의 디큐(dequeue) 역할을 하는 shift() 함수가 존재하기는 합니다만, 시간 복잡도가 O(n)입니다. 사실상 시간적으로는 디큐의 역할을 하지 못하는 것입니다.

index를 활용해서 큐의 시작점을 바꿀 수 있지만, 이 또한 공간적으로 디큐의 역할을 하지 못합니다.

그렇다고 연결리스트로 큐를 구현하기에는 너무 코드가 길어지고 코딩 테스트에서 활용하기 어렵습니다.

index와 delete 연산으로 해결하기

delete연산은 시간복잡도가 O(1)입니다. 다만 리스트의 길이가 줄어들지 않습니다.

 

const list = [0, 1, 2];
delete list[0];
list
// [ <1 empty item>, 2, 3 ]
list[0]
// undefined

 

그래서 head 역할을 하는 index와 함께 활용하면 큐처럼 디큐 동작을 할 수 있습니다.

 

아래는 큐를 사용하는 BFS 구현의 예제입니다.

shift 를 사용하는 예제

const q = [start];
while (q.length !== 0) {
  const node = q.shift();
  ...
}

delete 를 사용하는 예제

let head = 0;
const q = [start];
while (q[head] !== undefined) {
  const node = q[head];
  delete q[head];
  head += 1;
  ...
}

주의할 점

MDN Web Docs에 따르면 delete 사용 시 바로 메모리를 비우지는 않습니다.

하지만 메모리 초과가 나오던 코드가 delete 사용 시 통과하는 것으로 보아 사용하는 의미가 있다고 생각합니다.