[알고리즘] treeDFS

LMH·2022년 12월 24일
0

이번 포스팅에서는 깊이 우선 탐색 알고리즘에 대해서 정리하겠습니다.

tree 구조를 탐색하는 방법으로 깊이 우선 탐색(Depth-first-search)과 너비 우선 탐색(Breadth-first search)이 있습니다.

넓이 우선 탐색은 노드의 첫번째 자식 노드들을 우선적으로 탐색하여 그 노드가 자식노드를 가지지 않는 경우까지 탐색 후 그 부모의 형제 노드를 탐색하는 방법입니다. 트리 구조의 가장 깊은 곳까지 탐색한 후 다음 노드를 탐색합니다.

너비 우선 탐색은 노드의 자식요소를 모두 순회하여 탐색한 후 각 자식 요소의 자식노드들을 순차적으로 탐색하는 방법입니다. 깊이 우선 탐색과 다르게 같은 층의 노드를 순서대로 탐색합니다.

Tree 구조의 넓이 우선 탐색은 재귀를 이용하면 간단하게 해결할 수 있습니다.

[문제]

임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.

조건

  • 'value', 'children' 속성을 갖는 객체 (Node)
  • 'node.value'는 number 타입
  • 'node.children'은 Node를 요소로 갖는 배열
let dfs = function (node) {
  let values = [node.value];  
  for(child of node.children) {
    values = values.concat(dfs(child))   // 재귀를 이용하여 문제 해결
  }
    return values;
};

// 노드를 생성하는 함수
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 노드에 자식요소를 추가하는 함수
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};
profile
새로운 것을 기록하고 복습하는 공간입니다.

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN