자바스크립트를 활용한 bfs 구현

파이썬으로 코테를 준비하는 사람들은 대개 'deque' 를 활용하여 bfs를 구현할 것이다.

deque를 활용하면 큐에 노드를 넣어주고 빼주는 과정이 굉장히 빨라지기 때문에, 시간복잡도를 해결하기 위한 가장 기본적이면서도 강력한 방법으로 사용되고 있다.

 

사용 방법은 다음과 같다 (at 파이썬)

from collections import deque // deque 임포트 받기

q = deque() // 노드를 넣고 빼줄 큐 생성
q.append() // 노드 넣어주기
q.popleft() // 노드 빼주기, 큐에 들어있는 노드 중 가장 먼저 넣어준 노드를 빼줌

// 일반적으로 노드를 빼주는 것은 O(n)의 시간복잡도를 가지나, deque를 활용해 생성한 큐에서
// popleft를 활용해 빼준다면 O(1)의 시간복잡도를 가진다.

 

그러나 자바스크립트에선 파이썬에서처럼 쉽고 간편하게 deque를 임포트 받을 수 없다.

즉 자바스크립트로 코딩테스트를 준비하는 사람은 deque를 직접 구현하거나 다른 방법으로 bfs 문제를 해결해야 한다.

deque를 직접 구현하여 문제를 푸는 것은 코딩테스트 문제 풀이 시간 내에 해결하기 어려울 가능성이 높기 때문에, 조금은 다른 방법으로 bfs 문제를 해결해야 한다.

 

키 포인트는 '포인터의 활용'이다.

실제로 큐에서 노드를 빼주지 말고, 큐의 값을 읽어주는 포인터를 하나 생성하여 popleft 대신pointer ++를 해주는 것이다.

 

간단히 설명하자면 다음과 같다. (파이썬과 비교하여 설명)

 

case1) 파이썬

q = deque() -> 이 코드를 통해 선입선출이 가능한 큐를 생성한다.

q.append(Node) -> 이 코드를 통해 큐에 노드를 넣어준다.

now_node = q.popleft() -> 이 코드를 통해 큐에 들어가있는 노드 중 가장 먼저 들어가있는 노드를 큐에서 제거해준다. 제거된 노드는 now_node에 넣어주어 이후의 코드에서 활용해준다.

 

위의 순서대로 코드를 진행했을 경우 q의 모습은 다음과 같이 바뀐다.

[] -> [Node] -> []

 

case2) 자바스크립트

반면 자바스크립트에선 조금 다르다.

let q = [] -> 이 코드를 통해 큐를 생성해준다.

let pointer = 0 -> 이 코드를 통해 큐의 시작점을 지정해준다.

q.push(Node) -> 이 코드를 통해 큐에 노드를 넣어준다.

let nowNode = q[pointer] -> 이 코드를 통해 nowNode에 큐에 들어가있는 노드 중 가장 먼저 들어간 노드를 넣어준다.

pointer ++ -> 이 코드를 통해 q의 범위를 조절해준다. nowNode에 들어간 Node값은 더 이상 q에 들어있지 않은 것으로 간주한다는 것이다.

 

이 방법을 사용하면 기본적인 bfs를 사용할 때 작성되는 while문의 조건 또한 수정되어야 한다.

파이썬의 경우 while q: 로 조건을 걸고 q에서 더 이상 어떠한 노드도 뻬낼 수 없을 때 반복문을 종료한다면, 자바스크립트의 경우 while (pointer < q.length) 와 같은 방식으로 조건을 걸어야 한다. 포인터의 값이 q의 길이와 같아진다면 더 이상의 반복문은 수행되어선 안된다.

 

간단히 코드로 작성해보면 다음과 같다.

(백준 1260번 문제의 bfs 부분)

const readline = require('readline')
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
})

let input = []
let nodeLink = []

function bfs(n, m, v, nodeLinkList) {
    let q = []
    q.push(v)
    let pointer = 0
    let visited = Array(n + 1).fill(0)
    visited[v] = 1
    while (pointer < q.length) {
        let nowNode = q[pointer]
        console.log(nowNode)
        
        pointer ++
        for (let i = 0; i <= n; i++) {
            if (nodeLinkList[nowNode][i] === 1 && visited[i] === 0) {
                q.push(i)
                visited[i] = 1
            }
        }
    }
}

rl.on('line', (line) => {
    input.push(line)
}).on('close', () => {
    [n, m, v] = input[0].split(' ').map(Number)
    // console.log(n, m, v)
    for (let i = 0; i < m; i++) {
        nodeLink.push(input[i + 1].split(' ').map(Number))
    }
    // console.log(nodeLink)
    let nodeLinkList = []
    for (let i = 0; i <= n; i++) {
        nodeLinkList.push(Array(n + 1).fill(0))
    }
    // console.log(nodeLinkList)
    for (let i = 0; i < m; i++) {
        nodeLinkList[nodeLink[i][0]][nodeLink[i][1]] = 1
        nodeLinkList[nodeLink[i][1]][nodeLink[i][0]] = 1
    }
    // console.log(nodeLinkList)
    bfs(n, m, v, nodeLinkList)
})