깊이 우선 탐색(DFS, Depth-First Search) 이란?

깊이 우선 탐색(DFS, Depth-First Search)

깊이 우선 탐색 (DFS)는 하나의 순환 알고리즘으로 백트래킹에 사용하는 대표적인 탐색 알고리즘이다. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 주로, 재귀함수 또는 Stack으로 구현할 수 있다.

 

 

깊이 우선 탐색의 구현

1. 순환 호출 이용

def dfs_recursive(graph, start, visited = []):
## 데이터를 추가하는 명령어 / 재귀가 이루어짐 
    visited.append(start)
 
    for node in graph[start]:
        if node not in visited:
            dfs_recursive(graph, node, visited)
    return visited

2. 스택 

def dfs2(graph, start_node):
    ## deque 패키지 불러오기
    from collections import deque
    visited = []
    need_visited = deque()
    
    ##시작 노드 설정해주기
    need_visited.append(start_node)
    
    ## 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:
        ## 시작 노드를 지정하고
        node = need_visited.pop()
 
        ##만약 방문한 리스트에 없다면
        if node not in visited:
 
            ## 방문 리스트에 노드를 추가
            visited.append(node)
            ## 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])
                
    return visited

시간 복잡도와 장단점

• 인접 행렬에서의 시간 복잡도: O(V²)
• 인접 리스트에서의 시간 복잡도: O(V+E)
• V: 정점(노드)의 개수, E: 간선의 개수
• 장점
  • 현재 경로상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 든다.
  • 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함 (DFS와  BFS를 둘 다 사용해도 되는 문제)
    • ex) 그래프의 모든 정점을 방문하는 문제
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점:
  • 해가 없는 경로에 깊이 빠질 가능성이 있다.
    • 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다
  • 얻어진 해가 최단 경로가 된다는 보장이 없다.
    • 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

DFS를 활용하기 적합한 문제

• 경로의 특징을 저장해둬야 하는 문제 (경로 상의 노드를 기억해야하는 문제)

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

• 검색 대상 그래프 큰 문제 

목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있기 때문입니다.