깊이 우선 탐색(DFS)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 사용해보면서 배운 점을 정리한 글입니다.

그래프의 각 정점을 방문하는 그래프 순회에는 다양한 방법이 있으나 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 2가지로 나눌 수 있다. 우선 DFS에 대해 정리하고자 한다.

DFS(깊이 우선 탐색)란?

Depth First Search의 약자로 시작 노드에서 시작한 뒤 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 스택이나 재귀로 구현하는데 구현의 편의성으로 재귀로 작성된 풀이가 주를 이룬다. 노드의 방문 여부를 체크하지 않아 무한 루프에 빠지거나 stack 상태를 체크하지 않아 스택오버플로우가 발생하지 않게끔 주의해야 한다.

DFS의 특징

• 모든 조건을 만족하는 모든 경우의 수에 대해 탐색을 진행하고자 할 때 사용한다.
• 자기 자신을 호출하는 순환 알고리즘의 형태를 갖는다.
• 전위 순회 등 트리 순회는 DFS의 한 종류다.
• 검색 속도는 BFS(너비 우선 탐색)에 비해 느리다.
• 백 트래킹에 사용되는 알고리즘이다.

DFS의 장점

• 현재 경로 상의 노드만 기억하면 되기 때문에 저장 공간이 적게 요구된다.
• 목표 해가 깊은 곳에 있다면 빠르게 구할 수 있다.
• 구현이 BFS보다 쉽다.

DFS의 단점

• 해가 존재하지 않는 경우 계속해서 탐색을 진행할 가능성이 있다. (무한 루프에 빠질 가능성을 말한다. 임의의 종결조건을 선언하여 종료할 필요가 있음)
• DFS는 해가 도출되면 탐색을 종료하므로 구한 해가 최단 경로를 보장하진 않는다. 그래서 해가 다수일 경우 도출된 해가 최적해가 아닐 수 있으므로 해를 저장할 버퍼를 선언 후 저장된 해들에 대해 추가 탐색을 진행해야 한다.

DFS의 구현

재귀 구조로 구현

graph = {1: [2, 3, 4], 2: [5, 6], 3: [8],
         4: [8, 9],    5: [7],    6: [],
         7: [3],       8: [],     9: []}

def dfs_recursive(v, path=[]):
    path.append(v)
    for x in graph[v]:
        if x not in path:
            path = dfs_recursive(x, path)
    return path

print(f'dfs_recursive path: {dfs_recursive(1)}')

스택 구조로 반복문 구현

graph = {1: [2, 3, 4], 2: [5, 6], 3: [8],
         4: [8, 9],    5: [7],    6: [],
         7: [3],       8: [],     9: []}

def dfs_stack(start):
    stack = [start]
    path = []
    while stack:
        v = stack.pop()
        if v not in path:
            path.append(V)
            for x in graph[v]:
                stack.append(x)
    return path

print(f'dfs_stack path: {dfs_recursive(1)}')

실행 결과를 보면 모든 정점을 잘 방문하긴 했는데 순서가 조금 다르다. 재귀 구조는 깊이 탐색 시 삽입된 순서대로 계속 탐색하여 왼쪽 분기부터 타고 내려가지만 스택 구조는 삽입된 순서의 역순으로 pop()하기 때문에 오른쪽 분기부터 타고 내려가기 때문이다.