Udemy - 트리 순회(BFS/DFS)

트리 순회

이전 포스팅에서 이진 검색 트리(BST)를 학습하며 트리란 무엇인지, 그리고 트리의 기본적인 알고리즘적 활용법 등을 다뤘다.

따라서 트리의 개념 학습에서 그치는 것이 아니라, 이번 포스팅에서는 DFS와 BFS라는 트리 “탐색 기법”에 대해 정리해보고자 한다.

BFS	DFS
깊이 우선 탐색으로, Depth-First-Search의 약자다.	너비 우선 탐색으로, Breadth-First-Search의 약자다.

당연히 위의 개괄적인 설명만 읽고서는 DFS와 BFS를 이해할 수 없다. 따라서 각 탐색 기법을 기본 예제와 함께 더 자세히 설명해보도록 하겠다.

---

너비 우선 탐색(BFS)

위 gif에서 확인할 수 있듯, 너비 우선 탐색은 루트 노드에서 시작해 각 층별 노드들을 모두 훑으며 아래로 내려가며 탐색하는 순회법이다.

기본적으로 각 층에서 좌 → 우 방향으로 탐색을 하며, 각 층에 대한 노드 탐색이 끝나면 아래 층으로 향하는 것이 특징이다. 어떤 방향성을 갖고 탐색을 하는지는 이해했으니 바로 본론(코드)으로 넘어가보도록 하겠다!

BST를 활용한 BFS 구현

이진 검색 트리를 활용하여 BFS를 구현해보자.

위 사진의 이진 트리를 BFS를 활용하여 탐색하면, 결과가 [10, 7, 19, 3, 9, 25]가 될 것이다.

// 우선 위와 동일한 트리를 구성하기 위하여 앞선 포스팅에서 작성했던 BST insert 메소드를 활용했다.
const bst = new BST();
bst.insert(10);
bst.insert(7);
bst.insert(19);
bst.insert(3);
bst.insert(9);
bst.insert(25);

자, 이제 본격적으로 BFS를 통해 노드 탐색 결과를 배열로써 반환 받아보도록 하자.

// ...이전에 작성했던 BST 클래스는 생략

BFS() {
  let node = this.root;
  // queue는 탐색될 노드들의 대기열이라고 생각하면 된다.
  let queue = [];
  // result는 탐색된 노드들이 담길 최종 배열이다.
  let result = [];
  // 우선 초기 queue는 루트이기 때문에 기본적으로 root를 push해준다.
  queue.push(node);
  // 큐가 빌 때까지 반복한다.
  while (queue.length) {
    // Array.shift()는 제거된 요소를 반환해준다. 따라서 여기서의 node는 queue의 맨 앞 요소다.
    node = queue.shift();
    // 그리고 해당 요소를 result에 push해준다. (탐색이 됐으니까)
    result.push(node.val);
    // 그리고 해당 node의 left 또는 right값이 존재하면 각각 "차례대로" queue에 담아준다.
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return result;
}

queue에 대한 push를 left → right 순으로 해줬기 때문에 queue에는 left가 먼저, 그리고 그 다음에 right가 담기게 된다. 이는 선입선출법을 따른 것이므로, 우리가 의도했던 바와 같이 result 배열에는 각 층의 노드들이 왼쪽에서 오른쪽 순으로 담기게 되는 것이다.

위의 예제 BFS가 실행되는 과정은 위와 같다. (queue의 맨 앞 요소가 result에 담기고, result에 담긴 따끈한 요소의 left, right가 각각 queue에 차례대로 push 되는 것!)

---

깊이 우선 탐색(DFS)

이번에는 재귀를 사용해야 한다.
BFS와 반대로, 우선 최대한 깊게 노드들을 탐색한 뒤 우측 노드들을 탐색하는 방식이다.

탐색할 트리는 BFS에서 활용했던 트리와 동일하다.

DFS() {
    // 탐색 결과를 담을 result 배열
    let result = [];
    // 헬퍼 함수!
    function traverse(node) {
      // 1. 우선 타겟 노드를 result에 담는다.
      result.push(node.val);
      // 2. 그리고 해당 노드의 left가 존재한다면 traverse에 해당 노드의 left를 담아 재실행한다.(재귀)
      if (node.left) traverse(node.left);
      // 3. 위 left에 대한 작업들이 모두 끝나면 right에 대한 탐색이 실행된다.
      if (node.right) traverse(node.right);
    }
    traverse(this.root);
    return result;
  }

이렇게 작성한 DFS를 실행하면 [10, 7, 3, 9, 19, 25]이 반환되어야 한다.

---

DFS와 BFS는 언제 사용하는가?

항상 나오는 진부한 결론일 수 있지만.. 정답은 없다.
때에 따라 두 방법이 낼 수 있는 효율성이 달라지기 때문이다.

그리고 시간 복잡도는 두 방식 모두 동일하다. 노드 전체를 하나 하나 탐색해야하는 것은 같기 때문이다. 따라서 중요한 것은 공간 복잡도다. DFS와 BFS는 공간 복잡도 측면에서 어떤 차이점을 보일까?

트리가 넓으면 DFS를, 깊으면 BFS를…!!

성급한 일반화일 수도 있지만, 대개 이런 공식을 따르게 될 것 같다. 노드가 굉장히 많고 넓게 펼쳐진 트리를 상상해보자(좌측 트리). 이 때 우리가 BFS를 사용하면 큐에 이 수많은 노드들을 다 담아줘야 한다. 그렇게 처리한다면 공간 복잡도가 굉장히 높아질 것이기에, 이러한 경우에는 재귀와 콜스택을 사용하는 DFS를 활용하는 것이 효율적일 것이다.

하지만 반대로, (이런 경우는 거의 없지만) 한 쪽으로만 치우쳐진 거의 배열과 다름없는 트리(우측 트리)에 대해서는 BFS가 유리하다. 한 방향으로만 탐색을 하면 되기 때문에 shift와 push에 의해 큐가 메모리를 거의 차지하지 않기 때문이다. 그러나 DFS를 이러한 형태의 트리에 사용하게 되면, 매 노드마다 콜스택이 점유되기 때문에 BFS에 비해 효율성이 떨어지게 될 것이다.

따라서, 다시 정리하자면!!

좌우로 넓고 노드가 많은 트리에서는 DFS를, 한 쪽으로 깊게 치우친 트리에 대해서는 BFS를 활용하는 것이 공간복잡도 측면에서 효율적이다.

---