201229 - 알고리즘 ( BFS )

[토이12]

treeBFS

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

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

출력
배열을 리턴해야 합니다.

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

---

시도한 오답

let bfs = function (node) {

  let values = [node.value]
  // 너비가 1인 것부터 차례대로 처리해야하눈데.....
  node.children.forEach( (n) => {
    while (n <= node.length) {
      n++
    }
     values = values.concat(bfs(n))
  } )
  
  return values;
}

정답 ref

let bfs = function (node) {

  let queue = [node];           // 큐에 들어가는 것부터 
  const values = [];            // 반환값을 담을 그릇 = values
  while (queue.length > 0) {    // 인자 node에 뭔가 들어와 있으면,
    const head = queue[0];      // 일단 제일 앞의 노드를 head로 지정
    queue = queue.slice(1);     // head는 제외하고, 그 다음 노드부터를  queue array로 한다.

    values.push(head.value);    // head.value?? 이렇게 써야 하는군... 그냥 head로 하면 노통과
                                // 음.. 여기부터 헷갈리기 시작하는군...
    head.children.forEach( (child) => queue.push(child) ); // 큐에 하나씩 추가...
  }
  return values;

};

// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
  this.value = value;
  this.children = [];
};

// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) { 
  this.children.push(child);
  return child;
};
  // 위의 Node func에 프로토타입으로 addChild를 추가한다.
  // 그리고 그 addChild는 함수
  // child라는 어떤 인자가 들어오면, 위에 this.children이 배열이니까, 그 배열에 child를 하나씩 el로 추가한다.
  // 그리고 결과값인 child를 배출한다. (child는 배열의 형태이다)

// 휴아... 아너무피곤 자쟈윌리야 이제그만💕️

---

BFS (Breadth - First Search / 너비 우선 탐색)

• 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘

• 큐 자료구조를 이용한다. / 큐 👉️ 먼저 집어 넣은 데이터가 먼저 나오는 FIFO 구조로 저장

  1. 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다. (방문 기준 : 번호가 낮은 인접 노드부터)
  2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두(한번에) 큐에 삽입하고 방문 처리한다.
     (시작노드부터의 거리가 1인 경우가 가장 먼저, 그다음 2인 경우, 3인경우.. 순서)
  3. 더 이상 위의 2번의 과정을 수행할 수 없을 때까지 반복한다.

---

출처 : 동빈나님 유튜브 https://www.youtube.com/watch?v=7C9RgOcvkvo💚️