완전탐색 DFS, BFS

---

DFS (Depth First Search)

트리나 그래프 등에서 하나의 노드를 최대한 깊게 들어가면서 해를 찾는 탐색 기법

특징

1. 자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다. (재귀 or 스택)
2. 이 알고리즘을 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다는 것이다.
3. 검사하지 않을 경우 무한루프에 빠질 수 있다. ex) vistit[index] = true;
4. 미로를 탐색할 때, 해당 분기에서 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로(새로운 분기)로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
5. 모든 노드를 방문하고자 할 때, 이 방법을 선택한다.
6. 너비우선탐색(BFS)보다 더 간단하다.
7. 검색 속도 자체는 너비우선탐색(BFS)에 비해서 느리다.

 

• 장점: 인접한 후보 노드만 기억하면 되므로 적은 기억공간소요, 노드가 깊은 단계에 있을 경우 빠르게 정답 산출한다.
• 단점: 선택한 경로가 답이 아닐 경우 불필요한 탐색 가능, 최단 경로를 구할 시 찾은 해가 정답이 아닐 경우 발생한다.
• 구현 메서드
  • 재귀를 이용한 탐색
  • 스택을 이용한 탐색

 

DFS 구현

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const DFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...graph[node], ...needVisit];
    }
  }
  return visited;
};

console.log(DFS(graph, "A"));
// ["A", "B", "D", "E", "F", "C", "G", "H", "I", "J"]

 

---

 

BFS (너비 우선 탐색, Bread-First Search)

루트 노드(혹은 다른 임의의 노드) 에서 시작한 인접 노드를 먼저 탐색하는 방법

특징

1. BFS는 재귀적으로 동작하지 않는다.
2. 알고리즘 구현할 때 가장 큰 차이점은 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.(검사하지 않으면 무한루프에 빠질 수 있다.)
3. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐를 사용한다.
4. 선입선출 원칙으로 탐색한다. 
5. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
6. 깊게 탐색하기 전에 넓게 탐색한다.
7. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.

BFS 구현

const graph = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "G", "H", "I"],
  D: ["B", "E", "F"],
  E: ["D"],
  F: ["D"],
  G: ["C"],
  H: ["C"],
  I: ["C", "J"],
  J: ["I"]
};

const BFS = (graph, startNode) => {
  const visited = []; // 탐색을 마친 노드들
  let needVisit = []; // 탐색해야할 노드들

  needVisit.push(startNode); // 노드 탐색 시작

  while (needVisit.length !== 0) { // 탐색해야할 노드가 남아있다면
    const node = needVisit.shift(); // queue이기 때문에 선입선출, shift()를 사용한다.
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      needVisit = [...needVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(BFS(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

 

시간복잡도

DFS와 BFS는 노드 수 + 간선 수 만큼의 복잡도를 지닌다. 즉, O(n)

 

 

참조

https://dad-rock.tistory.com/645

https://velog.io/@sangbooom/JS-BFS-DFS