Post

[Algorithm, JavaScript] JS에서 효과적인 BFS 구현은 어떻게 해야할까 (백준-1303 : 전쟁-전투)

Posted Updated
By scorchedrice
10 min read
[Algorithm, JavaScript] JS에서 효과적인 BFS 구현은 어떻게 해야할까 (백준-1303 : 전쟁-전투)

간단한 BFS문제이지만 post를 작성하는 이유

python의 경우엔 다음의 명령어로 쉽게 bfs를 구현할 수 있다.

1

from collections import deque

JS로 언어를 바꾸면서 파이썬이 얼마나 사기였는지 매번 느낀다.

아무튼 해당 문제를 풀면서 JS로 queue를 어떻게 구현할 지 몰라 다음처럼 문제를 풀었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

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

// 전쟁 - 전투
// 위력의 정의 : N명이 뭉쳐있을 때, N**2 (대각 인접은 인접이 아님, 오로지 십자)
const NM = input.splice(0,1)
const [M, N] = NM[0].split(' ').map((numb) => Number(numb));
let matrix = []
for (let i = 0; i < N; i ++) {
    matrix.push(input[i].split(''))
}

let WPower = 0;
let BPower = 0;

// node로 queue 구현 어려우니 가라로 일단 구현해보자.
// 4방향 정의
const di = [0,0,1,-1]
const dj = [1,-1,0,0]

function bfs(si, sj) {
    let qI = [];
    let qJ = [];
    let count = 0;
    const pivot = matrix[si][sj];
    qI.push(si)
    qJ.push(sj)
    count ++
    matrix[si][sj] = count
    while (qI.length > 0) {
        // popleft를 구현 어떻게 할지 몰라서 그냥 앞에서 뺏다.
        const nI = qI.splice(0,1)[0]
        const nJ = qJ.splice(0,1)[0]
        for (let dir = 0; dir < 4; dir ++) {
            var nextI = nI + di[dir]
            var nextJ = nJ + dj[dir]
            if (0<=nextI && nextI < N && 0<=nextJ && nextJ<M && matrix[nextI][nextJ] === pivot) {
                // console.log('matrix value',matrix[nextI][nextJ], nextI, nextJ)
                qI.push(nextI)
                qJ.push(nextJ)
                count ++
                matrix[nextI][nextJ] = count
            }
        }
    }
    return count;
}

for (let i = 0; i < N; i ++) {
    for (let j = 0; j < M; j ++) {
        if (matrix[i][j] === 'W' || matrix[i][j] === 'B') {
            const teamColor = matrix[i][j];
            const power = bfs(i,j);
            // console.log(power)
            if (teamColor === 'W') {
                WPower += power**2
            } else {
                BPower += power**2
            }
        }
    }
}
console.log(WPower, BPower);

보면 알겠지만 python의 popleft()를 구현하지 못한 상태로 문제를 풀었다. 그래서 이 post를 작성한다.

저게 왜 문제가 될까

사실 답은 나오니까 문제는 없다. 근데, 시간복잡도가 낭비된다는 것은 부정할 수 없다. python의 deque, popleft()를 활용한 동작은 O(1)의 시간복잡도를 가진다. 하지만 내가 구현한 splice(0,1)[0], shift()와 같은 동작은 O(n)의 시간 복잡도를 가진다.

JS에서 O(1)의 BFS(queue)의 구현

크게 3가지 방법으로 구현할 수 있다.

  1. front값을 바꾸며 배열의 재배치 없이 queue 구현하기
  2. class로 queue 구현하기

배열의 재배치 없는 queue 구현

사실 이 방법은 오직 알고리즘을 풀 때만 의미있는 것 같다. 그래도 알고 있으면 좋은 스킬이라고 생각되기에 학습할 필요가 있다 생각..!

splice(0,1)[0], shift()와 같은 것들은 배열의 재배치가 필요한데, 이를 front 변수를 이동시키며 재배치를 진행하지 않고 큐와 동일한 기능을 하겠다는 것이다. 예시를 통해 확인해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function bfs(si, sj) {
    let qI = [];
    let qJ = [];
    let front = 0;
    let count = 0;
    const pivot = matrix[si][sj];
    qI.push(si)
    qJ.push(sj)
    count ++
    matrix[si][sj] = count
    while (qI.length > front) {
        const nI = qI[front]
        const nJ = qJ[front]
        front += 1
        for (let dir = 0; dir < 4; dir ++) {
            var nextI = nI + di[dir]
            var nextJ = nJ + dj[dir]
            if (0<=nextI && nextI < N && 0<=nextJ && nextJ<M && matrix[nextI][nextJ] === pivot) {
                // console.log('matrix value',matrix[nextI][nextJ], nextI, nextJ)
                qI.push(nextI)
                qJ.push(nextJ)
                count ++
                matrix[nextI][nextJ] = count
            }
        }
    }
    return count;
}

해당 방법도 정상적으로 답이 나오지만, 다이나믹한 변화는 없었다. (메모리만 좀 아낀 수준?)

class로 queue 구현하기

사실 class로 구현하는 방법도 두가지로 나눌 수 있다.

  1. 객체의 key-value 구조 (object)를 사용하여 구현할 것이냐
    • head, tail을 변경하면서, O(1)을 준수하는 Object를 활용하여 구현
  2. 연결 리스트 활용 구현
    • 1번의 경우 headIndex, tailIndex를 변경하며 구현했지만 연결리스트의 경우 연결된 노드들의 head, tail되는 노드를 확인하며 진행한다 생각하자.
    • 무슨말이냐면, 각 노드는 다음 값이 무엇인지 알기에, headNode, tailNode만 알아도 다음값을 알 수 있단 말임.
      • 따라서 Node를 생성하는 새로운 class 또한 정의해야 하기에 복잡할 수 있다.

우선 object를 활용한 구현 방법을 보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// 해당 클래스의 구현 방식 => head, tail을 바꾸고 O(1)을 준수하는 object를 사용하며 구현
class Queue {
    constructor() {
        this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }

    enqueue(item) {
        this.items[this.tailIndex] = item;
        // 추가 되었으니, tail ++
        this.tailIndex++;
    }

    dequeue() {
        if (this.isEmpty()) {
            // popleft를 할 때, 비어있다면 ..? 이 상황은 발생할 수 없음!
            return undefined;
        }
        const item = this.items[this.headIndex];
        // 값을 뽑아내고, 이를 return 함과 동시에 메모리에서 제거하는 작업 진행해야함.
        // 또한 값을 제거했으니 head ++
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }

    isEmpty() {
        return this.tailIndex - this.headIndex === 0;
        // tail과 head가 동일한 경우 ? => empty!
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

function bfs(si, sj) {
    let qI = new Queue();
    let qJ = new Queue();
    let count = 0;
    const pivot = matrix[si][sj];
    qI.enqueue(si)
    qJ.enqueue(sj)
    count ++
    matrix[si][sj] = count
    while (!qI.isEmpty()) {
        const nI = qI.dequeue()
        const nJ = qJ.dequeue()
        for (let dir = 0; dir < 4; dir ++) {
            var nextI = nI + di[dir]
            var nextJ = nJ + dj[dir]
            if (0<=nextI && nextI < N && 0<=nextJ && nextJ<M && matrix[nextI][nextJ] === pivot) {
                // console.log('matrix value',matrix[nextI][nextJ], nextI, nextJ)
                qI.enqueue(nextI)
                qJ.enqueue(nextJ)
                count ++
                matrix[nextI][nextJ] = count
            }
        }
    }
    return count;
}

그 다음은 연결 리스트를 활용한 구현 법을 확인해보자.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  
  enqueue(value) {
    const newNode = new Node(value);
    // 큐가 비어 있을 때
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 큐에 요소가 있는 경우
      // 다음 값 (포인터) 설정해주고 마지막 값 삽입.
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
  
  dequeue() {
    if (!this.head) return null;
    // 큐가 비어있는데 dequeue 불가 ..!
    const value = this.head.value;
    // return 해야하는 value (head Node value)
    this.head = this.head.next;
    // head Node를 재설정 해줌.
    this.size --;
    if (this.size === 0) {
      // 빈 큐가 된다면
      this.tail = null;
    }
    return value;
  }
}

이 경우에도 object 를 활용한 경우처럼 bfs를 사용하면 된다. (단 while문은 qI.size > 0 조건 설정)

결론

사실 백준에서 푼 문제는 큰 변화는 없었다. 시간이 그놈이 그놈이고 메모리도 그놈이 그놈이였다. 아마 테스트케이스가 큰 범위가 아니였기에 그랬을 것이라 생각한다.

해당 내용을 학습하면서 class에 대해 잘 알게 되었다는 느낌이 든다. 사실 해당 코드를 인터넷에서 찾았을 때, 이렇게 가지 해야하나? 싶었는데, 하나하나 읽어보니 이해가 되었다. 이와 같은 사고방식이 알고리즘 풀이에 도움이 될 것이라 생각한다. 앞으로도 당연한 것을 당연하게 생각하지 말고 고민하면서 성장해야겠다.

Algorithm, JavaScript
bfs 백준
This post is licensed under CC BY 4.0 by the author.