[JS] 왜 큐 클래스를 직접 구현하면 알고리즘 속도가 빨라질까?

최근 들어서 백준 알고리즘 문제들을 풀고있는 알린이(?)다.

여느 날과 같이 문제를 풀던중 시간초과가 발생하는 BFS 문제가 있어 관련 내용을 찾아보던 중 흥미로운 내용을 발견하였다.

큐 class를 직접 구현하여 문제를 푸는게 알고리즘 속도가 2~3배 정도 빠르게 나오는 것!!!!

관련하여 Javasrcipt의 배열과 큐 클래스를 활용하는 것이 어떤 차이가 있는지 찾아보았다.

---

문제 - 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

---

### 일반적인 BFS 구현

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

const [n, m, r] = input[0].split(" ").map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
}
graph.forEach((line) => line.sort((a, b) => a - b));
// console.log(graph);
const visited = new Array(n + 1).fill(0);

const queue = [];
queue.push(r);
visited[r] = 1;

let step = 1;
while (queue.length) {
    const cur = queue.shift();

    for (const next of graph[cur]) {
        if (!visited[next]) {
            queue.push(next);
            visited[next] = ++step;
        }
    }
}

console.log(visited.slice(1).join("\n"));

### 클래스 활용 구현

const input = require("fs").readFileSync("dev/stdin").toString().trim().split("\n");

class Que {
    q = [];
    h = 0;
    t = 0;
    enque(v) {
        this.q[this.t++] = v;
    }
    deque() {
        const v = this.q[this.h];
        delete this.q[this.h++];
        return v;
    }
    size() {
        return this.t - this.h;
    }
}

const [n, m, r] = input[0].split(" ").map(Number);
const graph = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= m; i++) {
    const [a, b] = input[i].split(" ").map(Number);
    graph[a].push(b);
    graph[b].push(a);
}
graph.forEach((line) => line.sort((a, b) => a - b));
// console.log(graph);
const visited = new Array(n + 1).fill(0);

const queue = new Que();
queue.enque(r);
visited[r] = 1;

let step = 1;
while (queue.size()) {
    const cur = queue.deque();

    for (const next of graph[cur]) {
        if (!visited[next]) {
            queue.enque(next);
            visited[next] = ++step;
        }
    }
}

console.log(visited.slice(1).join("\n"));

• 노란색을 표시된 부분이 큐 클래스를 구현한 알고리즘
• 초록색 표시된 부분이 기본적인 BFS 알고리즘
  
  

---

위 두 코드의 가장 큰 차이점은 당연하게도 클래스를 활용하여 구현한 큐를 활용했다는 것이다.

그렇다면 왜 큐를 클래스로 구현하였을때 알고리즘의 속도가 빨라진 것일까?

자바스크립트 배열의 .shift() 는 최악의 경우 O(n)의 시간 복잡도를 가진다.

.shift() 메소드의 경우 배열 맨앞의 요소를 삭제하고 앞부분의 요소부터 하나씩 앞으로 이동시켜야 하기 때문에 첫 번째 원소에 접근하는 시간을 O(1)로 해결할 수 있는 반면, 배열을 이용한 경우에는 배열 전체를 한 번 순회하면서 위치 재조정을 하는 시간까지 추가로 필요하기 때문에 다른 언어에서의 큐 자료구조보다 더 많은 시간이 소요된다.

반면, 구현한 큐 클래스의 경우 클래스로 구현한 Que 클래스에서는 배열의 특성을 고려하지 않고 직접 포인터를 조작하기 때문에 즉, 배열의 인덱스를 직접 조작하여 배열의 요소를 추가하고 삭제하여 배열을 재 조정 하지 않으며, 큐의 크기가 고정되어 있으므로 메모리를 보다 효율적으로 사용하여 알고리즘의 속도에서 차이가 발생한다.

const q = new Que()
for (i = 1; i <=3 ; i ++) {q.enque(i)};

console.log(q); //q: (3) [1, 2, 3]

q.deque();

console.log(q); //q: (3) [비어 있음, 2, 3]

---