[JavaScript] 자바스크립트 BFS 문제풀이 예시

BFS는 너비 우선 탐색입니다. 예전 포스트에 넓이(...) 라고 잘못 썼었더군요. 어제 수정했습니다.

Queue를 통해 구현되며, 가까운 레벨의 노드부터 탐색하면서 최단 거리를 찾는 문제에 많이 이용됩니다. 즉 DFS와 달리, 찾고자 하는 목표를 얻으면 바로 멈춰서 결과를 도출한다는 특징이 있습니다.

 

이런 트리가 있다면 DFS(전위 순회)는 1->2->4->5->... 의 순서겠지만, BFS는 1->2->3->4->5->6->7 의 순서가 되겠지요.

 

BFS는 방문한 노드를 다시 방문할 필요가 없기 때문에, 문제를 풀 때는 어떤 노드를 방문했는지 검사하는 리스트가 반드시 필요합니다.

 

 

문제 출처 : 프로그래머스 Lv. 3 '네트워크'

Solved-Algorithm/JavaScript/프로그래머스/3/43162. 네트워크 at main · ParkBible/Solved-Algorithm

문제 전문은 위 링크에서 볼 수 있습니다.

 

function solution(n, computers) {
    const ch = Array.from({length: n}, () => 0)
    let count = 0;
    
    const bfs = (start) => {    // (1)
        const queue = [start];
        ch[start] = 1;
        
        while (queue.length > 0) {    // (2)
            const now = queue.shift();
            
            computers[now].forEach((isConnection, idx) => {    // (3)
                if (now !== idx && isConnection === 1 && ch[idx] === 0) {
                    ch[idx] = 1;
                    queue.push(idx);
                }
            });
        }
    }
    
    for (let i = 0; i < ch.length; i++) {    // (4)
        if (ch[i] === 0) {
            bfs(i);
            count++;
        }
    }
            
    return count;
}

 

 

(4)에서 시작합니다. 체크 리스트를 확인하며 방문하지 않은 노드가 있다면 그 노드에서부터 시작하여, (1)을 통해 해당 네트워크의 모든 노드를 탐색하여 체크합니다.

 

탐색이 끝났다면, 체크 리스트를 마저 확인합니다. 그 다음 노드부터 방문했는지 확인하는 것입니다. 그러다가 방문하지 않은 새로운 노드가 발견되었다면 다시 탐색을 시작하는 것의 반복입니다.

 

읽다 보면 의아한 점을 느낄 수 있는데 그렇습니다... 이 문제는 트리 탐색만 하면 되는 문제라 DFS로도 풀 수 있습니다. 그저 탐색하는 노드의 순서만 다를 뿐이지요.

 

 

-BFS에 대한 설명-

(3)의 forEach문은 해당 노드와 연결된 노드를 찾는 작업입니다. 그 노드는 방문된 적이 없어야 합니다.

그런 노드가 발견되었다면, 큐에 노드를 넣고 방문했다고 체크 리스트에 기록합니다.

 

DFS라면 그런 노드를 찾았을 때 그 노드로 넘어가기 위해 자기 자신을 다시 호출하겠지요.

BFS니까, 일단 큐에 넣어놓습니다.

그러고 나서 자기랑 연결된 다른 노드가 더 있는지 forEach문을 계속 돕니다. 더 있다면 큐에는 노드가 더 쌓이겠지요.

 

그리고 큐에 있는 모든 노드를 빼내서 탐색할 때까지 (2)의 while문이 반복합니다.

 

 

-BFS 알고리즘 구현 3줄 요약-

- 자기 주변의 노드를 탐색하면서 큐에 넣어놓는다. (기록 필수)

- 그 바깥에 있는 반복문에서 큐에 담겨있는 노드를 하나씩 빼서 탐색한다. 즉 위의 과정을 반복한다.

- 이때, 뺀 노드가 내가 원하던 노드라면 break로 반복문을 빠져나간다. (위 문제는 무조건 모든 노드를 탐색해야 하기에 이런 조건은 없었음)

 

// 암기용 포맷
function bfs(graph, start) {
  const visited = new Set([start]); // 방문했던 노드 배열
  const queue = [[start, 0]]; // [노드, 거리]

  while (queue.length > 0) { // 큐가 빌 때까지
    const [node, dist] = queue.shift(); // 바로 shift

    for (const next of graph[node]) {
      if (!visited.has(next)) { // 방문한 적 없으면
        visited.add(next); // 방문목록에 추가
        queue.push([next, dist + 1]); // 큐에도 추가
      }
    }
  }
}

bfs(graph, 0);