[알고리즘] DFS, BFS 기본 구현

설명

DFS, BFS 처음 볼때에는 정말로 햇갈렸습니다. 하지만 DFS와 BFS의 원리를 알고

DFS의 D의 영어가 Depth(깊이) BFS의 B의 영어가 Breadth(폭, 너비) 라는 것을 알고 있으면 쉽게 햇갈리지 않을거라고 생각합니다.

 

순열, 중복순열, 멱집합에 대해 앞 게시글에 작성을 하였는데 전부 DFS로 작성을 하였습니다. 물론 BFS로 풀면 풀 수 있지만 효율의 문제여서 상황에따라 BFS, DFS를 잘 쓰는게 중요합니다.

그래서 제가 생각하는 BFS를 쓰는 경우에는 찾고자 하는 그래프의 깊이가 얕거나, 최단 경로를 찾아야할 때에 가장 유용한 방법 이라고 생각합니다.

 

BFS는 층에 개념으로 보는게 더 효율적입니다. 모든 층을 다 둘러 보았을때에 그 다음 층을 보러 가는 것입니다.

 

1.          사장

2.      부장  부장

3.    대리 대리 대리

4.사원 사원 사원 사원

 

위와 같은 예시로 한명씩 사람을 만난다고 가정했을때에

DFS의 경우에는 [ 사장, 부장, 대리, 사원, 사원, 대리,...] 순이지만

BFS의 경우에는 [ 사장, 부장, 부장, 대리, 대리, 대리 ...] 순 입니다.

 

그래서 BFS는 Queue이라는 개념을 사용하여 찾습니다.

[ 1.   사장   2.  부장  부장  3. 대리 대리 대리   4.사원 사원 사원 사원 ]

이렇게 일렬로 어느 한 변수에다가 순서대로 자료를 넣어주고 사장을 확인하면 확인한 값은 Shift로 빼주고

부장이 제일 앞으로 오게 만듭니다. 이런 상황을 반복하다가 변수에 있는 값이 모두 사라지게 되면은 그 때 함수가 종료되게 코드를 작성하면 됩니다.

 

큐에 자료가 있으면 아직 방문하지 않은 노드들이 있는 것이고, 모두 확인을 해주어야 하기 때문에 while 문의 조건문에 큐의 길이를 매번 체크 해주어 while문을 쓰면 편합니다.

 

문제

https://vvs1.tistory.com/67

12번 문제를 들고왔습니다. 임의의 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]

 

 

코드

let bfs = function (node) {
  // TODO: 여기에 코드를 작성합니다.
  let result = [];
  let queue = [node]; // 큐를 사용해줄 변수를 만듭니다.

  while(queue.length > 0){ // 큐의 길이가 0이되면은 반복을 종료합니다.
    let target = queue.shift(); // 큐를 사용하는 변수의 맨 앞에 값을 target으로 설정해주고
      result.push(target.value)  // 그 값을 출력할 result 변수에 대입합니다.
    for(let i = 0; i < target.children.length; i++){ // 타겟의 자식인자들이 있는지 확인하고
      queue.push(target.children[i]) 
      //그 인자들을 큐의 값 맨 뒤에 대입하여 result 변수에 들어 갈 수 있도록 합니다.
    }
  }
  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;
};

reference

위 코드는 반복문이지만 아래코드(reference)는 forEach로 해결한 모습

  let queue = [node];
  const values = [];
  
// while문 부분에서 이렇게 코드를 작성 할수 있습니다.  

  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;
};

 

while이라는 반복문에서

탐색하고자 하는 최상단층을 queue에 값을 넣고 결과값에 옮기면서

최상단층 자식인자들의 존재 여부를 확인하고 있다면 queue 변수 제일 뒤에 값을 넣어서

최상단층이 다 확인이 되면 자연스럽게 자식인자들이 확인이 될 수 있게 코드를 작성하는 것 입니다.

DFS라는 개념이 저는 좀 더 쉽다고 생각하기 때문에 DFS를 확인하고 BFS에 대해 고민하신다면 더 쉽고 빠르게 이해가 가능할 것이라고 봅니다.