문제 : treeDFS

DFS 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 한다.

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]

문제의 접근

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
};

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

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

문제에서 이미 클래스의 정의는 해두었다. 그렇다면 위 예시를 통해 나올 트리는 어느정도 예상이 가능하다. 이 트리를 깊이 우선 탐색(DFS : Depth-First Search) 순서로 값들을 넣어주면 된다.

처음에는 조금 어렵게 생각해서 인접행렬이나 인접리스트를 만들어서 순회하며 방문한 값들을 넣어주려고 했다. 하지만 그렇게 하면 자식들의 순서가 뒤집혀서 들어가는데 그렇다면 이 방법은 좋은 접근이 아니라고 생각되었다.

그렇다면 조금만 더 단순하게 생각해서 그 자식 값들을 앞에서 부터 조회하면서 값을 넣어주면 어떨까? 하는 새각을 했다. 물론 이 방식은 재귀함수를 필두로 한다.

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
 
  let auc = (obj) => {
    result.push(obj.value)
    if(obj.children.length === 0){
      return;
    }else{
      for(let i = 0; i < obj.children.length; i++){
        auc(obj.children[i]);
      }
    }
  }
  auc(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;
};

이 코드도 잘 실행 된다.
위 코드를 눈으로 읽는다면 전혀 이상 없이 결과값이 도출 되어야 한다. 하지만 그렇지 못했다. 콘솔창에 확인해보니 .value가 정의되어 있지 않다고 나왔다. 인자는 객체로 전달되었을 텐데 왜 실행이 되지 않는지 의문이 생겼다. 그래서 이 코드를 조금만 변경해 주었다.

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
  
  let auc = (value, children) => {
    result.push(value)
    if(children.lenght === 0){
      return;
    }else{
      for(let i = 0; i < children.length; i++){
        auc(children[i].value, children[i].children);
      }
    }
  }

  auc(node.value, node.children);
  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;
};

코드를 다음과 같이 변경해주니 정상적으로 테스트가 통과되었다. 단순히 콜백함수 안에 들어가기 전에 분해해 줬을 뿐인데 왜 첫번째 시도는 통과되지 않고 두번째는 순조롭게 통과가 되는지 의문이 생겼다.

문제를 통해 생각해 볼 것

문제에 대한 접근도 괜찮았고 해법도 무난했다고 생각된다. 하지만 다른 의문점이 생기게 되었는데 이 부분이 왜 그럴지 한번 고민해봐야 할 것 같다. 오탈자가 있었나보다 둘다 잘 실행된다.