[알고리즘/javascript] BFS

문제

임의의 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]

---

BFS란?

BFS는 가장 상위(root)노드와 인접한 노드들을 먼저 탐색하는 방법이다. 즉, 노드와 노드 사이에 연결과 무관하게 root 노드와 가까운 순서대로 가장 마지막에는 가장 끝에 존재하는 노드를 탐색하게 된다.

BFS 선택 시, 참고사항

• 노드와 노드 사이에 최단 경로를 찾고 싶을 때 사용하는 방법이다.
• 큐를 이용하여 구현한다.

---

 

코드

이진 트리 BFS 구현에는 자료구조 '큐'를 사용한다.

1. 큐 변수 = [ ], 방문한 노드의 value를 저장하는 변수 = [ ]. 변수 2개를 빈 배열로 선언한다.
2. 시작하는 노드(root)를 큐에 넣는다.
3. 큐 안에 값이 있는 한 반복문을 계속 실행하면서,
   1. 현재 노드를 Dequeue하고 현재 노드의 value를 노드의 value를 저장하는 변수에 추가한다.
   2. 만약 Dequeue 된 현재 노드가 left 프로퍼티를 가지고 있다면 큐에 추가한다.
   3. 만약 Dequeue 된 현재 노드가 right 프로퍼티를 가지고 있다면 큐에 추가한다.

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let queue = [node]; // root(시작 노드)를 배열에 넣은 상태로 큐를 선언, 초기화.
  const visitedNodeValues = []; // 방문한 노드의 정보를 담을 배열 선언.

  while (queue.length > 0) { // 큐에 요소가 있는 한 반복문 실행

    const currentNode = queue[0]; // 현재 노드
    queue.shift(); // Dequeue 시키기 (큐: 선입선출)

    visitedNodeValues.push(currentNode.value); // 현재 노드의 value를 방문한 노드의 value를 담는 배열에 추가

    currentNode.children.forEach((child) => queue.push(child)); // 탐색. 현재 노드의 자식노드들을 배열에 추가.
  }
  return visitedNodeValues;
};

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

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