DFS (깊이 우선 탐색)

DFS

많은 양의 데이터 중에서 원하는 데이터를 찾는 탐색의 기법 중 하나로

Depth First Search 말 그대로 깊이 우선 탐색입니다.

 

DFS 이해 1

 

그림과 같이 한 경로에서 끝을 보고 나서야, 다음의 탐색을 진행하는 탐색법이라고 보시면 되겠습니다.

 

DFS 이해 2

 

현재 노드에서 인접한 노드 중에서 방문하지 않은 정점을 발견하면 계속 탐색하는 유형이라고 볼 수 있습니다.

 

보통 BFS와 주로 비교하는데 각각의 장단점이 존재한다고 보시면 되겠습니다.

 

DFS와 BFS 비교

 

 

장점

• 현재 경로 상의 노드들을 기억하면 되므로 저장 공간이 비교적 적게 필요합니다.
• 목표 노드가 깊은 곳에 있으면 빠르게 도달할 수 있습니다.

 

단점

• 해가 없는 경로가 깊다면, 미로에 빠질 수가 있습니다.
• 목표 노드를 찾더라도, 이것이 최단 경로라고 확신할 수 없습니다. 

 

시간 복잡도

• 시간 복잡도는 O (노드의 합 |V| + 경로의 합 |E|) 입니다.

 

구현 코드 ( Python )

def dfs(graph, start_node):
    visit = list()
    stack = list()

    stack.append(start_node)

    while stack:
        node = stack.pop()
        if node not in visit:
            visit.append(node)
            stack.extend(graph[node])

    return visit