[알고리즘] DFS ( Depth First Search )

• DFS의 개념
• DFS에 대한 간단한 코드 설명
• DFS의 장단점
• LeetCode 예시 문제 및 예시 코드

DFS는 깊이 우선 탐색이라고 불리는 알고리즘이다.

해당 알고리즘은 보통 그래프 탐색을 하는 경우에 사용된다.

 

그래프 탐색이란 - 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말한다.

예를 들어, 특정 도시에서 다른 도시로 이동을 할 수 있는지 탐색하는 것이 될 수 있다.

 

그래프 탐색 방식 중의 하나로 DFS ( 깊이 우선 탐색)은 

그래프를 탐색 할때 , 깊이를 우선적으로 탐색하겠다는 전략이다. 

시작점부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다.

스택이나 재귀함수를 통해서 구현할 수 있는데 재귀 함수가 구현이 간편하기에 대부분 재귀 함수로 구현한다.

출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

해당 설명을 코드로 표현한 간단한 의사코드를 나타내면 아래와 같을 수 있다.

void search(Node root) {
  if (root == null) return;
  
  visit(root); // 1. root 노드 방문 (방문한 노드를 표시)
  
  // 2. root 노드와 인접한 정점을 모두 방문
  for each (Node n in root.adjacent) {
    if (n.visited == false) { // 3. 방문하지 않은 정점을 찾는다.
      search(n); // 4. root 노드와 인접한 정점 정점을 시작 정점으로 DFS를 시작
    }
  }
}

 

DFS의 장단점은 아래와 같을 수 있다.

 

장점 

• 현재 경로(branch)상의 노드들만 기억하면 되므로, 저장 공간의 수요가 비교적 적음 
• 코드가 직관적이고 상대적으로 구현하기 간단하다

단점

• 재귀함수를 이용하기 때문에, 함수 호출 비용이 추가적으로 들어간다
• 재귀 깊이가 지나치게 깊어지면 stack 메모리 비용을 예측하기 어렵다
• 최단 경로를 알 수 없다 ( 단지 해당 노드를 방문할 수 있냐 없냐 만 판단할 때 쓰기 적합하다)

---

예시문제

1026 Maximum Difference Between Node and Ancestor ( 조상과 노드 사이의 최대 차이값 )

joomn11.tistory.com/36

 

1448 Count Good Nodes in Binary Tree ( 이진트리의 Good 노드 갯수 )

joomn11.tistory.com/35

 

1038 Binary Search Tree to Greater Sum Tree ( BST를 GreaterSumTree로 변환 )

joomn11.tistory.com/33