깊이 우선 탐색(DFS) 알고리즘
개요
깊이 우선 탐색(Depth-First Search, DFS)은 그래프나 트리 자료구조에서 루트 노드(또는 임의의 시작 노드)에서 시작하여 한 분기(branch)를 최대한 깊게 탐색한 후, 더 이상 깊이 갈 수 없을 때 다른 분기로 이동하여 탐색을 계속하는 방법입니다. 즉, 가능한 한 깊이 내려간 후, 더 이상 내려갈 곳이 없으면 이전 노드로 돌아와 다른 경로를 탐색하는 방식입니다.
동작 원리
- 시작 노드를 방문하고, 해당 노드를 방문 처리합니다.
- 현재 노드에 인접한 노드들 중 방문하지 않은 노드가 있다면, 그 노드를 선택하여 재귀적으로 DFS를 수행합니다.
- 방문하지 않은 인접 노드가 없다면, 이전 노드로 돌아갑니다.
- 모든 노드를 방문할 때까지 위 과정을 반복합니다.
이러한 과정을 통해 DFS는 한 경로를 따라 최대한 깊이 탐색한 후, 다른 경로를 탐색하는 방식을 취합니다.
특징
메모리 사용량: DFS는 스택(Stack)을 사용하여 노드를 추적하므로, 재귀 호출을 통해 구현할 경우 시스템 스택 메모리를 사용하게 됩니다. 따라서 탐색 깊이에 따라 메모리 사용량이 증가할 수 있습니다.
완전성: DFS는 무한한 경로가 존재하지 않는 유한 그래프에서 모든 노드를 탐색하므로 완전성을 가집니다. 그러나 무한 그래프나 사이클이 존재하는 그래프에서는 무한 루프에 빠질 수 있으므로 주의가 필요합니다.
최적성: DFS는 최단 경로를 보장하지 않으므로 최적성이 없습니다. 이는 DFS가 경로를 따라 깊이 탐색하다가 해답을 찾으면 즉시 반환하기 때문에, 더 짧은 경로를 발견하지 못할 수 있기 때문입니다.
파이썬 구현 예시
def dfs(graph, node, visited):
if node not in visited:
print(node, end=' ')
visited.add(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
# 그래프를 인접 리스트로 표현
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# 방문한 노드를 추적하기 위한 집합
visited = set()
# DFS 함수 호출
dfs(graph, 'A', visited)출력 결과:
A B D E F C위 예시에서 그래프는 인접 리스트로 표현되었으며, DFS를 통해 'A' 노드부터 탐색을 시작하여 인접한 노드를 차례로 방문합니다.
시간 및 공간 복잡도
시간 복잡도: DFS는 그래프의 모든 노드와 모든 간선을 한 번씩 탐색하므로, O(V + E)의 시간 복잡도를 가집니다. 여기서 V는 노드의 수, E는 간선의 수를 의미합니다.
공간 복잡도: DFS는 재귀 호출로 인해 호출 스택에 최대 O(V)의 노드가 저장될 수 있으므로, 공간 복잡도는 O(V)입니다.
활용 예시
연결 요소 찾기: DFS를 사용하여 그래프의 연결 요소를 찾을 수 있습니다. 이는 그래프가 몇 개의 독립된 부분으로 이루어져 있는지 확인하는 데 사용됩니다.
위상 정렬: DFS는 위상 정렬(Topological Sorting)에서 사용됩니다. 이는 방향 그래프의 노드들을 선형으로 정렬하는 방법으로, 작업의 순서를 결정하는 데 활용됩니다.
강한 연결 요소 찾기: DFS는 그래프의 강한 연결 요소(Strongly Connected Components)를 찾는 알고리즘의 기본이 됩니다. 이는 그래프의 모든 노드가 서로 도달 가능한 부분 그래프를 의미합니다.
DFS는 이러한 특성과 활용도를 지니고 있어, 그래프 탐색 및 다양한 알고리즘의 기본으로 널리 사용됩니다.