알고리즘 11 : BFS 트리

treeBFS

문제

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

입력

인자 1 : node

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

출력

• 배열을 리턴해야 합니다.

주의사항

• 생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.

입출력 예시

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]

 

코드

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let queue = [node]
  let values = []
  while(queue.length>0){
    const head = queue.shift()
    values.push(head.value)
	//만약 children이 있다면
    if(head.children){
    //queue뒤쪽에 차례대로 push한다. queue는 나중에들어간게 나중에 빠지니깐
      head.children.forEach(el=>{queue.push(el)})
    }
  }return values
};

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

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

 

설명

레퍼런스를 보고 이해가가지 않아 그림을 그려보았다.

 

const root = new Node(1);
root.addChild(new Node(2));
root.addChild(new Node(3));
bfs(root) = [1, 2, 3];

위의 경우를 생각해보자.

root 노드는 위 처럼 node.value = 1, node.children = [Node(2),Node(3)] 으로 이루어져 있다.

 

이전에 정리한 글 중에 BFS는 Queue, 반복문을 사용하고 DFS는 Stack, 재귀함수를 사용하면 더 원활하게 문제를 해결할 수 있다는 내용이 있다.

 

이 문제는 BFS라고 명시되어 있으므로 Queue와 반복문을 사용한다.

 

 

let queue = [node] // queue에 현재 node를 넣어준다.
let values = [] // 리턴할 배열 선언
  
while(queue.length>0){
 const head = queue.shift()
 values.push(head.value)
 
 if(head.children){
   head.children.forEach(el=>{queue.push(el)})
 }
}

return values

 

첫번째 턴

queues는 빈배열이 되었다가 다시 head.chidren의 요소들로 채워진다.

두번째 턴

세번째 턴

이후는 queue가 빈배열이므로 while이 실행되지 않는다.

 

만약 children이 있다면 Queue의 맨 뒤로 차례차례 push되어서 다시 탐색된다.

 

이는 BFS탐색과 같다.

코드스테이츠 자료