알고리즘: 너비 우선 검색

트리 및 그래프 순회는 코딩 인터뷰에서 인기 있는 주제입니다. 그래프 순회에 대한 많은 접근 방식이 있지만 가장 일반적이고 친숙해야 할 중요한 것 중 하나는 BFS(Breadth First Search)입니다. 알고리즘의 기본 아이디어와 몇 가지 구현 예를 살펴보겠습니다.

기본 사항

Breadth First Search는 그래프 데이터 구조를 순회하는 데 사용되는 알고리즘입니다. 노드를 방문하는 순서입니다. 이름에서 알 수 있듯이 순회는 너비 우선 방식으로 수행됩니다. 즉, 특정 노드에서 시작하여 더 깊은 수준에서 추가 노드를 탐색하기 전에 현재 수준의 모든 노드를 순회합니다.

트리 순서 순회

루트 노드(6)에서 시작하여 각 레벨을 왼쪽에서 오른쪽으로 탐색한 후 다음 레벨로 이동합니다.

구현

BFS 알고리즘은 일반적으로 데이터 구조를 사용하여 반복적으로 구현됩니다. 큐에 루트 노드를 추가하여 시작합니다. 그런 다음 대기열을 반복하면서 노드를 제거하고 해당 자식을 대기열에 추가합니다. 이를 통해 레벨별로 그래프 레벨을 탐색할 수 있습니다.

문제

이진 트리가 주어지면 레벨 순회별로 레벨을 나타내는 하위 배열의 배열을 반환합니다.

class Node {
  constructor(val) {
    this.val = val
    this.left = null
    this.right = null
  }
}

해결책

const bfs = (root) => {
 const result = []
 const queue = [ root ]

 while (queue.length) {
   const level = []
   const qLength = queue.length
   for (let x = 0; x < qLength; x++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left !== null) queue.push(node.left)
      if (node.right !== null) queue.push(node.right)
   }
  result.push(level)
 }
 return result
}