[알고리즘] treeBFS

이번 포스팅에서는 너비 우선 탐색 알고리즘에 대해서 정리하겠습니다.

tree 구조를 탐색하는 방법으로 깊이 우선 탐색(Depth-first-search)과 너비 우선 탐색(Breadth-first search)이 있습니다.

넓이 우선 탐색은 노드의 첫번째 자식 노드들을 우선적으로 탐색하여 그 노드가 자식노드를 가지지 않는 경우까지 탐색 후 그 부모의 형제 노드를 탐색하는 방법입니다. 트리 구조의 가장 깊은 곳까지 탐색한 후 다음 노드를 탐색합니다.

너비 우선 탐색은 노드의 자식요소를 모두 순회하여 탐색한 후 각 자식 요소의 자식노드들을 순차적으로 탐색하는 방법입니다. 깊이 우선 탐색과 다르게 같은 층의 노드를 순서대로 탐색합니다.

[문제]

임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 너비 우선 탐색(BFS, Breadth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.

조건

• 'value', 'children' 속성을 갖는 객체 (Node)
• 'node.value'는 number 타입
• 'node.children'은 Node를 요소로 갖는 배열

let bfs = function (node) {
  let queue = [node];
  const values = [];
  while (queue.length > 0) { // queue가 빈 배열이 될 때 까지 반복
    const head = queue[0];  // queue의 첫 번째 요소를 head에 할당 
    queue = queue.slice(1);  // queue 첫 번째 요소 제거

    values.push(head.value);  // head의 값을 추가

    head.children.forEach((child) => queue.push(child)); 
    // head에 자식이 있을 경우 자식들을 queue에 추가하여 들어온 순서대로 value 값을 추가
  }
  return values;
};

// 노드를 생성하는 함수
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 노드에 자식요소를 추가하는 함수
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};