자바스크립트 검색 알고리즘 3 : Depth First Search

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. Depth First Search(DFS)

Breadth First Search(BFS)가 각 level에서 좌 → 우로 돌면서 탐색했다면, Depth First Search(DFS)는 가장 아래쪽 level까지 내려갔다가 끝에 다다르면 가장 가까운 조상으로 거슬러 올라간 뒤 탐색하지 않은 다른 자식 노드, 즉 형제 노드들을 탐색하는 방식이다. 글로는 설명이 어렵고 아래 사진이 이해하기에 직빵이다.

 

DFS 로직

 

DFS의 경우, chlid node에 대한 pointer를 기록할 필요가 없기 때문에 BFS보다 메모리를 적게 사용한다는 장점이 있다.

 

2. DFS 구현의 3가지 방식 : PreOrder, InOrder, PostOrder

위와 같은 Graph를 DFS로 탐색한다고 할 때, 탐색의 순서는 크게 3가지가 존재한다.

- PreOrder는 [ 33, 101, 105 ]

- InOrder는 [ 101, 33, 105 ]

- PostOrder는 [ 33, 105, 101 ] 순서로 stack에 담기게 된다.

 

//        9
//   4        20
// 1   6   15   170

Inorder : [1, 4, 6, 9, 15, 20, 170] // Binary Search Tree일 경우 정렬된 상태로 보여져서 유용하다.
PreOrder : [9, 4, 1, 6, 20, 15, 170]
PostOrder : [1, 6, 4, 15, 170, 20, 9]

위와 같은 Binary Search Tree의 경우에는 저러한 순서로 담기게 된다. 그리고 각 방식에는 각각의 장점이 있다.

InOrder 방식으로 탐색할 경우, 값이 최소값부터 최대값으로 정렬된 상태로 담기기 때문에 정렬이 필요할 경우에 유용하다. PreOrder는 Tree의 모양대로 담기기 때문에 Tree를 재창조할 때 유용하다고 한다.

 

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  DFTPreOrder(currentNode, list) {
    return traversePreOrder(this.root, []);
  }
  DFTPostOrder(){
    return traversePostOrder(this.root, []); 
  }
  DFTInOrder(){
    return traverseInOrder(this.root, []);
  } 
}

function traversePreOrder(node, list){
  list.push(node.value);
  if(node.left) {
    traversePreOrder(node.left, list);
  }
  if(node.right) {
    traversePreOrder(node.right, list);
  }
  return list;
}

function traverseInOrder(node, list){
  if(node.left) {
    traverseInOrder(node.left, list);
  }
  list.push(node.value);
  if(node.right) {
    traverseInOrder(node.right, list);
  }
  return list;
}

function traversePostOrder(node, list){
  if(node.left) {
    traversePostOrder(node.left, list);
  }
  if(node.right) {
    traversePostOrder(node.right, list);
  }
  list.push(node.value);
  return list;
}


const tree = new BinarySearchTree();
tree.insert(9)
tree.insert(4)
tree.insert(6)
tree.insert(20)
tree.insert(170)
tree.insert(15)
tree.insert(1)
// tree.remove(170);
// JSON.stringify(traverse(tree.root))

console.log('BFS', tree.BreadthFirstSearch());
console.log('BFS', tree.BreadthFirstSearchR([tree.root], []))
console.log('DFSpre', tree.DFTPreOrder());
console.log('DFSin', tree.DFTInOrder());
console.log('DFSpost', tree.DFTPostOrder());

//     9
//  4     20
//1  6  15  170

function traverse(node) {
  const tree = { value: node.value };
  tree.left = node.left === null ? null : traverse(node.left);
  tree.right = node.right === null ? null : traverse(node.right);
  return tree;
}

 

BFS는 queue를 이용해서 먼저 들어온 node부터 차례로 처리했다면, DFS는 stack 자료구조를 활용한다. 왜냐하면 DFS 로직을 구현하는 과정에 재귀 함수를 활용하기 때문에, 더 이상 child node가 존재하지 않을 때까지 콜스택의 상단에 계속 쌓이게 되고, 끝에 다다랐을 경우부터 하나씩 pop up되면서 값이 담기기 때문이다.

 

3. BFS vs. DFS

BFS, DFS 두 방식 모두 어쨌든 Worst Case에서는 모든 노드 전체를 traversing 해야 하기 때문에 시간 복잡도는 O(n)이 된다. 다만 둘의 검색 알고리즘이 다르기 때문에 서로 유용한 상황이 다르다. 항상 강조하지만 언제, 어떤 것을 선택해야 하는지, 그 이유는 왜 그러한지를 아는 것이 가장 중요하다.

 

# BFS

- 장점 : root에서 가까운 level부터 우선적으로 탐색하기 때문에 최단거리를 찾을 때 아주 유용하다. 

- 단점 : queue에 각 노드의 정보를 기록해야 하기 때문에 메모리를 잡아먹는다.

따라서 찾고자 하는 target node가 root node로부터 가까이 있다고 예상될 경우 BFS를 사용한다. 따라서 구글 맵에서 특정 위치까지 최단거리로 안내할 때, 또는 페이스북에서 친구 추천 등을 할 때 BFS를 사용할 수 있다.

 

# DFS

- 장점 : 메모리를 덜 잡아먹고, 또한 자식노드가 존재하는지에 대한 물음을 기반으로 탐색하기 때문에, 특정 경로가 존재하는지(Does Path Exist?)를 판단할 때 아주 유용하다.

- 단점 : BFS보다 속도가 느릴 수 있다.

따라서 DFS는 미로 게임 같은 곳에서 경로가 존재하는지를 판별할 때 사용할 수 있다.

 

//If you know a solution is not far from the root of the tree:
BFS : 위에서부터 시작하기 때문에 멀지 않게 찾을 수 있으므로

//If the tree is very deep and solutions are rare: 
BFS : DFS를 쓰면 아주 오랜 시간이 걸릴 것(very deep하므로)

//If the tree is very wide:
DFS : BFS는 메모리 공간을 너무 많이 잡아먹을 것이기 때문에

//If solutions are frequent but located deep in the tree:
DFS

//Determining whether a path exists between two nodes:
DFS : path가 존재하는지 찾을 때는 DFS

//Finding the shortest path:
BFS : 최단거리를 찾을 때는 BFS