[DFS 트리완전탐색 - 코플릿]

문제

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

입력

• 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]

 

문제풀이

먼저, let Node 부터 아래코드는 쭉 트리를 구성하기 위한 코드이다.

그다음에 의문점이 들었던건 let dfs 로 정의해놓은 함수에 node로 들어오는 인자가 뭐지 했는데 입출력 예시에 아주 잘 적혀있었다;;ㅎㅎ

node에는 객체가 들어오는데, { values, children : [~~~] } 이런 식으로 구성이 되어있다.

따라서, 리턴은 배열을 해야하니까, value값을 일단 배열에 넣고 chlidren을 돌면서 다시 재귀식으로 시작해야한다.

 

처음에 적었던 내 답안

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = [node.value];
  
  if (node.children){
  	for(const el of node.children){
    	arr = arr.concat(dfs(el));
    }
  }
  return arr
};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
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) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = [node.value];

  for (const el of node.children){
    arr = arr.concat(dfs(el))
  }
  return arr
};

let dfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let arr = [node.value];
  node.children.forEach(el => {
    arr = arr.concat(dfs(el));
  })
  return arr
};