[알고리즘] DFS(깊이 우선 탐색) 알고리즘 및 구현(파이썬)

목차

• DFS의 개념
• DFS의 장단점
• DFS의 시간 복잡도
• DFS의 구현

 

 

 

DFS(깊이 우선 탐색)이란?

• DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름
• 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘
• 스택 자료구조 또는 재귀 함수를 이용함

 

 

DFS의 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 존재하면 그 노드를 스택에 넣고 방문 처리를 합니다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼냅니다. 
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. 

 

 

 

DFS의 장단점

장점

• 현재 경로 상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 
• 목표 노드가 깊은 단계에 있을 경우 답을 빨리 구할 수 있다. 

 

단점

• 답이 없는 경로에 깊이 빠질 가능성이 있다. 이 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표 노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다. 
• 얻어진 답이 최단 경로가 된다는 보장이 없다. 목표에 이르는 경로가 다수인 문제에서 DFS는 경로를 찾으면 탐색이 종료되므로 이때 얻어진 경로가 최적이 아닐 수 있다. 

 

 

 

DFS의 시간 복잡도

• N: 노드의 수, E: 간선의 수
• 인접 리스트로 표현된 그래프: O(N+E)
• 인접 행렬로 표현된 그래프: O(N^2)

 

 

 

DFS의 구현

스택을 사용하지 않고 재귀 함수를 이용해 Python으로 구현

# graph[i]는 i번째 노드와 인접한 노드 번호를 포함
graph = [
    [1, 2, 4],
    [0, 2],
    [0, 1, 3, 4],
    [2, 4],
    [0, 2, 3]
]

# 방문 처리를 위한 리스트
visited = [False] * 5

# DFS
def dfs(v):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end = ' ')     # 0 1 2 3 4
    # 방문하지 않은 인접 노드 방문
    for x in graph[v]:
        if not visited[x]:
            dfs(x)

# 0번 노드부터 DFS 실행
dfs(0)

 

 

 

 

참고

• github.com/ndb796/python-for-coding-test
• https://ko.wikipedia.org/wiki/깊이_우선_탐색
• C언어로 쉽게 풀어쓴 자료구조