[코테 js] 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]

코드 작성

let dfs = function (node) {
  let result = [];
  result.push(node.value);
  for (let i = 0; i < node.children.length; i++) {
    result = result.concat(dfs(node.children[i]));
  }
  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;
};

문제 이해

깊이 우선 탐색(DFS)은 자료 구조를 탐색하는 방법 중 하나로, 이름에서 알 수 있듯이 깊이를 우선으로 탐색하는 방법입니다. 말로 설명하는 것보다 그림으로 보시면 이해가 더욱 쉽습니다.  (출처: 위키백과)

 

깊이 우선 탐색

애니메이션

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전

풀이

1. 우선, result라는 빈 배열을 선언하여 최초 입력된 노드를 입력합니다.

let result = [];
result.push(node.value);

 

2. node.children에 자식 노드들이 배열의 형태로 담겨있으므로, for문을 실행합니다. 각 자식 노드마다 또 자식 노드들이 존재하므로 재귀함수(자신을 포함하는 함수)를 사용합니다. ( dfs(node.children[i]) )

concat으로 result에 더한 값을 result에 다시 할당해 주어야 유지가 됩니다.

for (let i = 0; i < node.children.length; i++) {
  result = result.concat(dfs(node.children[i]));
}

 

3. 마지막으로 for문이 완료되면 result를 반환해줍니다

return result

 

깊이 우선 탐색 문제는 은근히 자주 사용되지만, 익숙하지 않으면 어려울 만한 개념입니다. 반면에 익숙해지면 그렇게 어렵지 않은 개념이기도 해서, 자주 접하여 익숙하게 만드는 게 중요한 것 같습니다.

더 좋은 풀이법이나 궁금한 점이 있으시면 댓글 부탁드립니다.