Tree DFselect(깊이 우선 탐색)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

• 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사함
• 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다
• 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

Tree {
  value: 1,
  children: [
    Tree { value: 2, children: [Array] },
    Tree { value: 3, children: [Array] }
  ]
}
// 들어오는 형태

            1

       2       3

    4   5   6   7

1. filter(callback)으로 노드의 값을 넣어서 true인 것만 result로 push

2. 모든 탐색이 완료되면 result를 push

3. depth를 확인하는 filter도 존재

4. recursion을 호출할 때 depth를 1씩 증가시켜준다.

Tree.prototype.DFSelect = function(filter) {
  let result = [];
  
  let recur = function(node, depth) {
    if (filter(node.value, depth)) {
      result.push(node.value);
    }
    if (node.children.length > 0) {
      for (let i = 0; i < node.children.length; i++) {
        recur(node.children[i], depth + 1);
      }
    }
  };
  recur(this, 0);
  
  return result;
};

깊이 우선 탐색의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 지님
• 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것
  (이를 검사하지 않을 경우 무한루프에 빠질 위험이 있음)