[JS]_daily coding #27

코플릿 데일리 코딩 06_treeDFS

문제

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

입력

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

출력

배열을 리턴해야 합니다.

입출력 예시

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]

문제 접근

예시에서 생성자 함수(Node)와 메소드(addChild)를 통해서 만든 root 객체를 출력한다면,아래와 같다.

{
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4, children: [] },
        { value: 5, children: [] },
      ],
    },
    { value: 3, children: [] },
  ],
}

이 root객체를 시작으로 깊이 우선 탐색을 하면 1, 2, 4, 5, 3의 순서로 탐색을 해야한다.

여기에 Node(6), Node(7)을 추가하면, 1, 2, 4, 6, 5, 3, 7 순서로 탐색해야 한다.

{
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4, children: [{ value: 6, children: [] }] },
        { value: 5, children: [] },
      ],
    },
    { value: 3, children: [{ value: 7, children: [] }] },
  ],
}

코드

재귀함수를 만들어서 풀었다. node의 value를 결과배열에 담고 children 배열에 각각 재귀 함수를 적용한다. for문을 통해서 children 배열에 요소가 한 개가 아닐 경우에는 0번 인덱스 객체에 먼저 접근하게 된다. (계속 0번 객체 만 깊이로 방문하다가) 말단 노드의 children이 빈배열일 경우에는 value만 result에 담고 for문은 실행하지 않는다. 그 다음에는 상위 노드의 1번 인덱스 객체(형제 노드)가 있으면 접근하는 식으로 깊이 우선 탐색이 이루어진다.

let dfs = function (node) {
  let result = [];
  const recursion = function (node) {
    //console.log(node.value);
    result.push(node.value);
    for (let i = 0; i < node.children.length; i++) {
      recursion(node.children[i]);
    }
  };
  recursion(node);
  return result;
};

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

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

레퍼런스 코드

let dfs = function (node) {
  let values = [node.value];

  node.children.forEach((n) => {
    values = values.concat(dfs(n));
  });

  return values;
};

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

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

더 공부할 것

• 재귀, dfs