[Algorithm] 너비 우선 탐색 (Breadth-First Search)

너비 우선 탐색이란?🤷🏻‍♂️

너비 우선 탐색 (Breadth-First Search)이란 그래프 탐색 방법 중 하나로서 루트 노트를 시작으로 인접한 노드 순으로 차례대로 탐색하는 탐색법이다. 즉 루트 노드를 시작으로 최대한 깊이 내려간 뒤
옆으로 이동하는 깊이 우선 탐색(DFS)와는 다르게 가까운 정점순으로 방문하고 멀리있는 정점들을 순회하고 큐(Queue)의 선입선출(FIFO)특성을 통해 구현할 수 있다.

너비 우선 탐색의 특징 🕺

• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
• 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 기본적이다.
• 너비를 우선 탐색하기에 답이 되는 경로가 여러개인 경우에도 최단경로임을 보장한다. 즉 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만, 너비 우선 탐색으로 현재 노드에서 가까운 곳부터 탐색할 경우, 탐색 시 먼저 발견되는 해답이 곧 최단거리기 때문입니다.

BFS의 알고리즘 구현 시 가장 중요한 원리는 Queue에 최상위 노드(Root Node)를 넣고, Queue에서 노드 하나를 Pop()한 뒤, Queue에서 Pop한 노드의 자식노드들을 전부 Queue에 넣는다. 그리고 Queue에 더이상 Pop() 할 수 있는 Node가 없을때까지 이 작업을 반복한다.

구현 👋

let bfs = function (node) { // BFS function
  
  let answer = [];
  let queue = [];

  if (answer[0] !== node.value) { 
    queue.push(node); // 첫 탐색 시 queue에 루트 노드를 push한다.
  }
  
  while (queue.length) { // pop() 해야할 노드가 남아있다면,
    let curr = queue.shift(); // queue의 가장 맨앞 노드를 뺀 뒤 변수에 할당.
    answer.push(curr.value); // 결과 배열에 curr의 value를 push한다.

    if (curr.children) { // 만일 queue에서 제거했던 노드가 자식 요소가 있다면,
      for (let i = 0; i < curr.children.length; i++) {
        queue.push(curr.children[i]); //queue에 자식 요소를 삽입한다.
      }
    }
  }
  return answer;
};

// ====================================================

let Node = function (value) {
  this.value = value;
  this.children = [];
};

Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};