Algorithm 20 : treeBFS

설명

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

예시

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]

생각

BFS는 노드의 같은 너비에 있는 자식들을 순회하는 방법이므로 queue를 통해 노드를 저장하고, value를 따로 저장하는 queue를 만든다.

풀이

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
let queue = [node]
let values = [node.value]
while(queue.length > 0 ){
  const head = queue.shift()
  for(let i=0;i<head.children.length;i++){
    values.push(head.children[i].value)
    queue.push(head.children[i])
  }
}
return values
};

깨달은 점

코드를 작성하고 디버깅을 통해서 queue에 담겨있는 노드를 꺼내 그 자식의 value를 배열에 담고 자식노드를 queue에 담음으로써 루트와 같은 너비에 있는 자식노드를 먼저 탐색할 수 있음을 이해할 수 있었다.