[Algorithm] treeBFS 알고리즘 Javascript Node.js 구현하기

 

 

treeBFS 알고리즘

 

문제

임의의 트리를 구성하는 노드 중 하나의 Node 객체를 입력받는다. 해당 Node를 시작으로 BFS(Breadth First Search) 알고리즘을 사용해서 전체 트리를 검색한다. 모든 Node의 value를 담은 배열을 반환한다.

 

입출력

• 'value', 'children' 속성을 가지는 객체
• typeof node.value = number;
• typeof node.children = arr[Node]

 

예를 들어 입출력이 다음과 같이 주어질 때 전체 트리의 모습은 3 level로 구성된다. BFS 알고리즘은 동일 레벨을 우선적으로 탐색하기 때문에 최종적인 결과는 [1,2,3,4,5,7,6]이 될 것이다.

 

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));

 

BFS(너비 우선탐색) 알고리즘은 코드로 구현할 때 Queue를 사용한다. 데이터 입력은 뒤로 추가되고, 출력은 앞방향에서 나오면서 전체 트리를 검색한다.

 

반대로 DFS(깊이 우선 탐색) 알고리즘을 사용하는 경우 재귀 함수 호출을 사용하는게 일반적이다. leaf 노드 까지 검색을 진행한 후 다음 자식 노드를 검색한다.

BFS 알고리즘을 사용할 경우 자식노드 전체를 검색하여 queue에 push하기 때문에 최종적으로 모든 자식노드를 검색하는 방향으로 탐색이 진행된다. 위 트리 검색 결과 중 Queue에 삽입되는 데이터들은 다음 순서로 저장된다.

 

Javascript Code 구현

 

BFS에서는 Queue 자료구조를 사용한다. 입력받은 인수가 객체기 때문에 먼저 배열에 추가해준 뒤 while문을 사용해서 queue 배열이 모두 출력될 때 까지 반복을 진행한다.

let Node = function (value) {
    this.value = value;
    this.children = [];
  };
  
  Node.prototype.addChild = function (child) {
    this.children.push(child);
    return child;
  };
  
  let bfs = function (node) {

    const queue = [node];
    const result = [];

    while(queue.length > 0){
        const temp = queue.shift();

        result.push(temp.value);

        if(temp.children){
            queue.push(...temp.children);
        }
    }

    return result;
  };

 

 

 

[Algorithm] powerSet 알고리즘,문자열 부분 집합 문제 Javascript, Node.js

 

[Algorithm] 백준 2447번 별 찍기 - 10 Node.js Javascript

 

[Algorithm] Binary Search 알고리즘 Javascript (반복, 재귀, 트리구조)