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

이번 포스팅에서 다룰 내용은 그래프 탐색 기법 DFS, BFS 중 하나인 깊이 우선 탐색 DFS 알고리즘입니다. 스택이나 재귀 함수를 사용해 구현됩니다. DFS 개념, 탐색 과정, 시간 복잡도, 장단점, 깊이 우선 탐색 알고리즘 파이썬 구현 방법 2가지, 예제까지 알아보겠습니다.

 

DFS (Depth First Search)

시작 노드부터 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 그래프 탐색 방법입니다.

한 방향으로 경로를 탐색하다가 더 이상 갈 수 없으면 다른 방향으로 탐색을 진행합니다.

Stack이나 재귀 함수(Recursive function)로 구현됩니다.

 

DFS(깊이 우선 탐색) 방법

1. 시작 정점에서 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색합니다.

2. 더 이상 갈 곳이 없으면, 가장 마지막에 탐색했던 갈림길 간선이 있는 정점으로 되돌아옵니다.

(이 전의 정점으로 다시 되돌아가는 과정에서 후입 선출(LIFO) 구조의 스택을 사용합니다.)

3. 돌아간 정점에서부터 다시 1,2번 과정을 반복하여 모든 정점을 방문할 때까지 순회합니다.

DFS-탐색과정

DFS 탐색 순서: A B D E C

 

시간 복잡도와 장단점

• 인접 행렬에서의 시간 복잡도: O(V²)
• 인접 리스트에서의 시간 복잡도: O(V+E)
• V: 정점(노드)의 개수, E: 간선의 개수
• 장점: 현재 경로상의 노드들만 기억하면 되므로 저장공간이 비교적 적게 들고, 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있습니다.
• 단점: 해가 없는 경로에 깊이 빠지면 시간이 오래 걸리고, 목표 노드까지의 경로가 다수인 문제에서 구한 해는 최적(최단 경로)이 아닐 수가 있습니다.

DFS 알고리즘 파이썬 구현 방법

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A'],
    'D': ['B'],
    'E': ['B']
}

- graph: 위에 사진 속의 그래프를 dict 형식으로 저장

- visited: 방문한 정점 list

 

(1) Stack을 활용한 DFS 알고리즘 구현

1. 시작 정점 start_node를 방문합니다.

2. 현재 정점 now_node에 인접한 정점 중에서

  2-1. 방문하지 않은 정점이 있다면, now_node를 스택에 push 하고 방문 안 한 정점에 방문하고 now_node로 바꿉니다.

  2-2. 방문하지 않은 정점이 없으면, 탐색 방향을 바꾸기 위해 스택을 pop 하여 마지막 방문 정점을 now_node로 합니다.

3. 모든 정점을 방문할 때까지 2번 과정을 반복합니다.

다만, stack을 활용할 때 사용하는 list의 pop()은 연산 속도가 느려서 성능면에서 불리한 단점이 있습니다.

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

    # 시작노드 스택에 저장
    stack.append(start_node)

    # 모든 노드를 방문할 때 동안
    while stack:
        now_node = stack.pop()

        if now_node not in visited:
            visited.append(now_node)
            stack.extend(graph[now_node])

    return visited

print(dfs(graph, 'A'))

 

(2) 재귀 함수(recursion)를 활용한 DFS 알고리즘 구현

def dfs_recursion(graph, start_node, visited=[]):
    visited.append(start_node)

    for node in graph[start_node]:
        if node not in visited:
            dfs_recursion(graph, node, visited)

    return visited

print(dfs_recursion(graph, 'A'))

 

DFS 깊이 우선 탐색 예제

[Python] SW Expert Academy - 4871. 그래프 경로

[Python] SW Expert Academy - 4871. 그래프 경로

---

그래프 탐색 방법 중 하나인 DFS Depth First Search 깊이 우선 탐색 알고리즘을 재귀 함수, stack 2가지 방법으로 파이썬 코드로 구현해보고 장단점, 시간 복잡도, 예제까지 알아보았습니다.