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

1. DFS 알고리즘이란

• 그래프 탐색 알고리즘의 한 종류
• 그래프 탐색이란 한 정점으로부터 시작하여 다른 정점을 차례대로 모두 한번씩 방문하는 것
• DFS는 Depth First Search의 약자로서, 임의의 정점에서 시작하여 다른 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다.

---

2. DFS의 특징

• 모든 노드를 방문하고자 할 때 이 방법을 선택함
• 넓게 탐색하기 전에 깊이 탐색함
• 자기 자신을 호출하는 순환 알고리즘의 형태를 가짐
• 전위 순회를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류임
• 어떤 노드를 방문했는지 여부를 반드기 검사해야 무한 루프에 빠지는 것을 방지할 수 있음
• 백트래킹에 사용됨

---

3. 장점

• BFS(너비 우선 탐색)보다 구현이 간단함
• 현재 경로 상 노드만 기억하면 되기 때문에 저장 공간이 적게 요구됨
• 목표값이 깊은 곳에 있다면 빠르게 찾아낼 수 있음

4. 단점 

• BFS에 비해 탐색 속도가 느림
• 해가 존재하지 않는 경우 계속 탐색을 진행할 가능성이 있음, 임의의 종결 조건을 선언하여 탐색을 종료할 필요가 있음
• 해가 도출되면 탐색을 종료하므로 최적의 해가 아닐 가능성이 있음

---

5. DFS를 사용해야 하는 문제

1) 경로의 특징을 저장해야 하는 문제 

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용(BFS는 경로의 특징을 가지지 못함)

 

2) 그래프의 크기가 정말 클 때

 

※ 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용해도 상관없음

---

6. 구현

1) 재귀로 구현

graph = {1: [2, 3, 4], 2: [5, 6], 3: [8],
         4: [8, 9],    5: [7],    6: [],
         7: [3],       8: [],     9: []}
 
def dfs_recursive(node, visited_path=[]):
    visited_path.append(node)
    for v in graph[node]:
        if v not in visited_path:
            recursive_dfs(v, visited_path)
    return visited_path
    
print(f'dfs_recursive path: {dfs_recursive(1)}')

 

2) 스택으로 구현

def dfs_stack(start_node):
    visited_path = []
    stack = [start_node]
    while stack:
        parent = stack.pop()
        if parent not in visited_path:
            visited_path.append(parent)
            for child in graph[parent]:
                stack.append(child)
    return visited_path
    
print(f'dfs_stack path: {dfs_stack(1)}')

인접 정점을 한번에 stack에 추가한다는 점에서 BFS처럼 보일 수 있으나 DFS가 맞다. 후입된 정점을 pop으로 선출하기 때문이다.