문제 : treeBFS

노드의 탐색을 treeBFS 탐색 순으로 배열에 담아서 내는 함수를 작성

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));
let output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5]

leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5, 7, 6]

문제의 접근

원리만 이해한다면 쉽게 구현할 수 있는 문제다. DFS는 stack으로 BFS는 queue 이 사실 하나만 기억한다면 쉽게 구현이 가능하다.

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
  let queue = [node]; // 조회할 노드들을 순차적으로 넣는다.

  while(queue.length > 0){ // 조회할 노드가 모두 빠져나가면 그만한다.
    let target = queue.shift(); // 노드를 하나 지정한다.
    result.push(target.value) // 대상 노드의 값을 결과에 저장해 준다.
    for(let i = 0; i < target.children.length; i++){
      queue.push(target.children[i])
    }// 자식의 노드들을 순차적으로 queue에 쌓아준다.
  }
  return result;
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};

모든 노드를 순서대로 조회하기 때문에 넓이 우선 탐색이 구현되게 된다.

문제를 통해 생각해 볼 것

DFS에 이어서 BFS 부분도 확실하게 내용을 이해 했다고 생각된다. 약간의 오탈자를 제외하고는 한번에 코드를 구현 할 수 있었다.