[JS] 알고리즘 문제풀이 11

Tree(트리) 자료구조 깊이 우선 탐색(DF select)

노드 1을 시작으로 차례대로 노드 9까지 순회한다. 진행되는 방향을 보면 한 가지의 끝까지 탐색하고, 그 다음 가지를 순차적으로 탐색한다. 전체적 위에서 아래로 깊게 탐색이 진행되는 것을 볼 수 있다.

예를 들면, 미로에서 한 루트로 계속 가다가 막다른 길이면 바로 직전 갈림길로 돌아가 길을 찾는 것이라고 할 수 있다. 깊이 우선 탐색은 전체 노드를 맹목적으로 탐색할 때 사용한다. 깊이 우선 탐색의 구현에서 중요한 것은 스택이다.

 

노드 3과 연결된 노드는 노드 2뿐이며, 이미 방문했으므로 이번 분기의 탐색이 완료된 것이기 때문에 노드 3을 스택에서 빼낸다.

스택의 가장 위에 위치한 노드 2와 연결된 아직 방문하지 않은 노드가 있는지 확인한다. 그러나 존재하지 않기 때문에 노드 2를 스택에서 빼낸다.

 

Javascript로 구현

let Tree = function(value) {
  this.value = value;
  this.children = [];
};
 
Tree.prototype.DFSelect = function(filter) { //여기서 filter은 가상의 함수
  let result = []; //일종의 스택 
  function check(tree, depth) {
    if(filter(tree.value, depth)) {
      result.push(tree.value)
    }
    if(tree.children) {
      tree.children.forEach(child => check(child, depth+1))
    }
  }
  check(this, 0)
  return result
};
 
 
/*
 * child를 추가합니다.
 * (Tree가 아닌 값이 들어올 경우, Tree 객체 형태로 변환 후 추가합니다.)
 */
Tree.prototype.addChild = function(child) {
  if (!child || !(child instanceof Tree)) {
    child = new Tree(child);
  }
 
  if (!this.isDescendant(child)) {
    this.children.push(child);
  } else {
    throw new Error('That child is already a child of this tree');
  }
  // 편의를 위해 추가된 child node를 return합니다.
  return child;
};
 
/*
 * 주어진 tree가 이미 해당 tree 혹은 sub tree의 child인지 확인합니다.
 */
Tree.prototype.isDescendant = function(child) {
  if (this.children.indexOf(child) !== -1) {
    // `child`는 해당 트리와 연결된 하위 노드를 의미합니다.
    return true;
  } else {
    for (let i = 0; i < this.children.length; i++) {
      if (this.children[i].isDescendant(child)) {
        return true;
      }
    }
    return false;
  }
};
 
/*
 * child를 삭제합니다.
 */
Tree.prototype.removeChild = function(child) {
  let index = this.children.indexOf(child);
  if (index !== -1) {
    // child를 삭제합니다.
    this.children.splice(index, 1);
  } else {
    throw new Error('That node is not an immediate child of this tree');
  }
};
 

 

 

 

Reference

 

velog.io/@sohi_5/algorithmDFS