[알고리즘] DFS (깊이 우선탐색)이란

 

깊이 우선탐색 (Depth-Firtst Search)

 

깊이우선 탐색이란?

루트노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이라고한다.

즉, 깊게 탐색, 완벽탐색

 

사용하는경우 

모든 노드를 방문 하고자 하는 경우에 이방법을 선택한다.

 

특징 

1. 자기자신을 호출하는 순환 알고리즘의 형태를 가지고있다.

2. 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다.

 

 

 

DFS의 애니메이션 출처 : 위키피디아

 

원리

위의 그림을 보면서 아래 설명을 봐보자.

1. 시작 정점을 1로 설정

2. 1번 탐색 시작 1번과 연결되었고 방문 안한 정점이 어디지? 2번이 있네. 2번으로 가자.

3. 2번과 연결되었고, 방문 안한것? 3번이네. 3번으로 가자.

4. 3번은? 4번이 있네. 4번으로 가자.

5. 4번은? 없는데..?? 그러면 3번으로 다시 올라가자.

6. 3번은? 방문 안한곳이 없네.. 다시 2번... 다시 1번

7. 1번은? 5번이 있네. 5번으로 가자.

-> 이런 식으로 방문 안한 곳이 없을때까지 반복

 

이런식으로 쭉 탐색을 한다. 이런식으로하면 한길로 깊이 있게 파고들어가게 된다. 이래서 깊이 우선탐색이라는 말이 나온것이다.

 

 

장단점

장점

코드가 직관적이고, 구현하기 쉽다.
-> 사실 일정행동을 계속 반복하는데, 이를 만들어놓고 끝까지 계속 돌려 쓰는 것이기 때문에 비교적 간단하게 코드를 구현할 수 있다.

 

단점

깊이가 엄청 깊어지면, 메모리 비용을 예측하기 어렵다.
-> 앞서 설명한 것처럼 깊이가 깊어질수록 함수가 하나씩 쌓이는 구조이다. 이 때문에 깊이가 엄청 깊어진다면 스택 메모리가 지나치게 커질 수 있다.

 

또한 최단 경로를 알 수 없다.

 

코드

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"]