너비우선탐색 (BFS) 코플릿 풀기

treeBFS

문제

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

입력

인자 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));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = bfs(root);
console.log(output); // --> [1, 2, 3, 4, 5]

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

 

 

---

너비우선탐색?

너비 우선 탐색은 그래프의 모든 정점을 방문하는 알고리즘 중 하나 

BFS는 시작 정점에서부터 거리가 가까운 정점부터 탐색을 진행하는 방식으로 동작함 . 즉 먼저 인접한 모든 정점을 방문하고 그 다음에 정점들과 인접한 정점들을 방문하여 계속해서 탐색을 확장해나감 

최단 경로 문제를 푸는데 유용하게 사용됨 .
구현은 큐를 이용하여 구현하는데 큐에 시작 정점을 넣고 큐에서 하나의 정점을 꺼내어 인접한 정점들을 큐에 넣는 방식으로 BFS 를 구현할 수 있음 

풀이 

let bfs = function (node) {
  
   let queue = [node];
  const values = [];
  while (queue.length > 0) {
    const head = queue[0];
    queue = queue.slice(1);

    values.push(head.value);

    head.children.forEach((child) => queue.push(child));
  }
  return values;
};


let Node = function (value) {
  this.value = value;
  this.children = [];
};

BFS는 큐를 이용해 문제를 풀 수 있으므로 처음 인자로 받은 node를 큐에 할당한다.  values 는 너비우선탐색의 결과를 저장할 배열이다. 그 후 큐가 비워질 때 까지 while문을 실행하여 큐의 가장 앞에 있는 원소를 head 로 두고 다시 큐에는 head를 제외한 원소를 할당한다 . 그 후 valuse에 head의 값을 push 한 후 .head와 연결된 자식들을 모두 큐에 넣는다. 이렇게 큐가 비워질 때까지 계속 반복한다.

 

만약 1이 루트 노드이고 자식으로 2 , 3 , 4 /  2의 자식으로 5 ,6 이 있다고 가정할 때 처음 1이 head 에 할당되고 1은 values에 push 된다. 그 후 head 의 자식인 2,3,4 는 forEach에 의해  큐에 push된다. while문의 조건을 만족하므로 계속 실행되고 큐의 가장 앞에있는 2 가 head가 되고 3,4는 queue에 남아있는다.  2는 values에 push 되고 2의 자식인 5,6 이 큐에 push 된다 . 그럼 현재 values 에는 1,2 가 queue 에는 3,4,5,6 순서로 존재한다. 이렇게 큐의 특징인 FIFO 을 만족하며 먼저 들어온 순서로 큐를 빠져나와 values에 할당된다.