[알고리즘] Depth First Search

ansmeer008·2022년 11월 5일
1

알고래즘

목록 보기
3/11
post-thumbnail

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

깊이 우선 탐색은 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식 (출처 : 위키)

문제에서 node는
'value', 'children' 속성을 갖는 객체
'node.value'는 number 타입
'node.children'은 Node를 요소로 갖는 배열

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

//TODO
let dfs = function (node) {
  let values = [node.value];
  //이러면 현재 노드 자체의 value값을 가진 values라는 배열이 만들어짐

  node.children.forEach((n) => {
    values = values.concat(dfs(n));
  });
  //재귀를 이용해 자식 노드 배열을 순회하면서 values라는 배열과 재귀로 리턴되는 배열들을 concat를 통해 합친다. 

  return values;
};                   

// 주어진 코드 1 : Node를 생성
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 주어진 코드 2 : 생성된 Node에 child를 추가하는 코드 
//** membership check(중복 확인)를 따로 하지 않습니다.**
Node.prototype.addChild = function (child) {
  this.children.push(child);
  return child;
};


profile
예술적인 코드를 짜는 프론트 엔드 개발자가 꿈입니다! (나는야 코드 아티스트! 🤭)

0개의 댓글