이번 포스팅에서는 깊이 우선 탐색 알고리즘에 대해서 정리하겠습니다.
tree 구조를 탐색하는 방법으로 깊이 우선 탐색(Depth-first-search)과 너비 우선 탐색(Breadth-first search)이 있습니다.
넓이 우선 탐색은 노드의 첫번째 자식 노드들을 우선적으로 탐색하여 그 노드가 자식노드를 가지지 않는 경우까지 탐색 후 그 부모의 형제 노드를 탐색하는 방법입니다. 트리 구조의 가장 깊은 곳까지 탐색한 후 다음 노드를 탐색합니다.
너비 우선 탐색은 노드의 자식요소를 모두 순회하여 탐색한 후 각 자식 요소의 자식노드들을 순차적으로 탐색하는 방법입니다. 깊이 우선 탐색과 다르게 같은 층의 노드를 순서대로 탐색합니다.
Tree 구조의 넓이 우선 탐색은 재귀를 이용하면 간단하게 해결할 수 있습니다.
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
let dfs = function (node) {
let values = [node.value];
for(child of node.children) {
values = values.concat(dfs(child)) // 재귀를 이용하여 문제 해결
}
return values;
};
// 노드를 생성하는 함수
let Node = function (value) {
this.value = value;
this.children = [];
};
// 노드에 자식요소를 추가하는 함수
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};