[알고리즘/javascript] DFS

문제

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

• 'value', 'children' 속성을 갖는 객체 (Node)
• 'node.value'는 number 타입
• 'node.children'은 Node를 요소로 갖는 배열

출력

• 배열을 리턴해야 합니다.

주의사항

• 생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.

입출력 예시

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]

leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = dfs(root);
console.log(output); // --> [1, 2, 4, 6, 5, 3, 7]

---

DFS란?

DFS는 가장 상위(root)노드에서 시작하여 다음 brach, 즉 root 노드와 연결되어진 3개의 노드 중 가장 좌측을 1번 branch, 그 우측으로 2번 branch라고 할 때, 1번 branch에서 2번 branch로 넘어가기 전에 해당 1번 branch와 관련되는 모든 노드를 탐색한 후, 2번 branch로 넘어가는 알고리즘을 말한다.
(여기서는 위에 그림을 참고하여 볼 수 있도록 노드가 3개라고 명시하였지만, 노드의 수는 변하는 값이다.)
DFS 선택 시, 참고사항

• 모든 노드의 탐색이 필요한 경우 이 방법을 선택한다.
• BFS(너비 우선 탐색)보다 더 간단한 알고리즘 형태를 띈다.
• 검색 속도는 BFS(너비 우선 탐색)보다 느리다.
• 스택 또는 재귀함수로 구현한다.

---

코드

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let answer = [node.value];
  //재귀 사용하여 자식 노드 탐색
  node.children.map((n) => {
    answer = answer.concat(dfs(n));
  })

  return answer;
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};