[코테 js] treeBFS 너비 우선 탐색(BFS, Breadth First Search)

문제

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

let bfs = 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;
};

입력

인자 1 : node

• 'value', 'children' 속성을 갖는 객체 (Node)
• 'node.value'는 number 타입
• 'node.children'은 Node를 요소로 갖는 배열

출력

• 배열을 리턴해야 합니다.

주의사항

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

입출력 예시

let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));             //          1
let leaf1 = rootChild1.addChild(new Node(4));            //        /   ＼
let leaf2 = rootChild1.addChild(new Node(5));            //       2      3
let output = bfs(root);                                  //     /  |    /
console.log(output); // --> [1, 2, 3, 4, 5]              //    4   5   7
                                                         //   /
leaf1.addChild(new Node(6));                             //  6
rootChild2.addChild(new Node(7));
output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5, 7, 6]

문제 이해

DFS와 BFS

BFS는 지난 포스팅으로 다뤘던 DFS와 비교되는 개념으로, 최상단 노드로부터 가까운 노드들부터 탐색하는 방식입니다.

treeDFS 깊이 우선 탐색 글

풀이 💡

입출력 예시를 이미지로 나타내면 다음과 같습니다.

여러 풀이법이 있지만 저는 코드가 짧은 재귀함수로 구현해 보도록 하겠습니다.

let bfs = function (node) {
    if (!Array.isArray(node)) node = new Array(node); 
    if (node.length == 0) return []; 
    return node.map((x) => x.value).concat(bfs([].concat(...node.map((x) => x.children))));

우선 재귀함수를 사용할 것이기 때문에, node가 배열이 아닌 경우에만 배열로 만들어 줄 것입니다.

첫 실행에만 node가 Node객체 이고, 두 번째 반복부터는 Node객체가 담긴 배열이 들어옵니다.

이해가 안되면, 건너뛰고 두 번째 반복 때부터 어떤 차이가 있는지 디버깅을 하면 이해가 될 것입니다.

if (!Array.isArray(node)) node = new Array(node);

재귀함수의 Base Case로 node의 길이가 0, 빈 배열이 들어오면 빈 배열만 리턴을 합니다.

이 부분이 없다면 빈배열에서 value를 찾으려 하기 때문에 에러가 뜰 것입니다.

if (node.length == 0) return [];

마지막으로 Recursive Case는 배열의 값들이 node객체이고 node.value를 각각 해주어야 하기 때문에

map((x) => x.value)를 사용하였고, node.children들의 배열을 bfs 함수로 탐색하여 합해야 합니다.

이때 node.children 또한 배열이므로, 그냥 실행하면 중첩 배열이 될 것입니다.

[ [node2의 children], [node3의 children]]

전개연산자(...)를 붙여주어 외부의 배열을 벗겨냅니다.

[node2의 children], [node3의 children]

ES6에서 중첩 배열을 없애는 방법으로 [].concat()을 사용하여 내부 배열을 하나로 합칩니다.

[node2의 children, node3의 children]

그러면 마지막 빈 배열이 나올 때 까지 반복 실행된 후 종료됩니다.

[1] + bfs([node2, node3])

[1] + [2, 3] + bfs([node4, node5, node7])

[1] + [2, 3] + [4, 5, 7] + bfs([node6])

[1] + [2, 3] + [4, 5, 7] + [6]

= [1, 2, 3, 4, 5, 7, 6]

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