DFS 알고리즘 (Depth First Search)
DFS 알고리즘은 그래프를 탐색하기 위한 대표적인 알고리즘 중 하나입니다. 이 알고리즘은 그래프의 깊이를 우선적으로 탐색하는 방식으로 동작합니다. DFS 알고리즘은 스택을 사용하여 구현될 수 있으며, 재귀적인 형태로도 구현할 수 있습니다.
개념
DFS는 탐색 시작점부터 출발하여 현재 노드와 인접한 노드들 중 하나를 선택하여 계속해서 탐색해나가는 알고리즘입니다. 선택된 노드가 다시 인접한 노드를 선택한 뒤 계속 탐색을 진행합니다. 이 과정을 반복하다가 더 이상 탐색할 수 없는 상태가 되면, 이전에 선택한 노드로 돌아가서 다음으로 탐색할 노드를 선택합니다. 이를 반복하여 모든 노드를 탐색할 수 있습니다.
동작 과정
- 탐색 시작점을 스택에 넣고 방문 표시를 합니다.
- 스택이 빌 때까지 다음 과정을 반복합니다.
- 스택에서 하나의 노드를 꺼냅니다.
- 해당 노드를 방문합니다.
- 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문 표시를 합니다.
- 모든 노드를 방문할 때까지 탐색을 계속합니다.
예제
다음은 DFS 알고리즘을 이용하여 그래프를 탐색하는 예제입니다.
def dfs(graph, start):
stack = [start]
visited = set()
while stack:
node = stack.pop()
visited.add(node)
print(node, end=" ") # 현재 노드 출력
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
# 그래프 정의
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
# DFS 탐색 시작
dfs(graph, 'A')위 예제에서는 그래프 구조를 딕셔너리로 표현하였습니다. 그래프의 각 노드를 키로, 해당 노드와 인접한 노드들을 값으로 표현하였습니다. DFS 함수는 시작 노드를 받아서 스택을 초기화하고, 방문한 노드들을 기록하기 위한 집합을 생성합니다. 그 후, 스택이 빌 때까지 다음 과정을 반복합니다. 스택에서 하나의 노드를 꺼내서 방문 표시를 합니다. 그리고 해당 노드와 인접한 노드 중 방문하지 않은 노드를 스택에 넣고 방문 표시를 합니다. 마지막으로, dfs(graph, 'A')와 같이 함수를 호출하여 탐색을 시작합니다.
시간 복잡도
DFS 알고리즘의 시간 복잡도는 각 노드와 간선을 한 번씩 방문하므로, O(V+E)입니다. 여기서 V는 노드의 수, E는 간선의 수를 나타냅니다.
마무리
DFS 알고리즘은 그래프를 탐색하기 위해 깊이를 우선적으로 탐색하는 방식을 사용합니다. 스택을 활용하여 구현할 수 있으며, 재귀적인 형태로도 구현할 수 있습니다. DFS 알고리즘을 이용하면 모든 노드를 탐색하거나, 특정한 조건을 만족하는 노드를 찾을 수 있습니다. 이러한 특징을 이해하고 적절히 사용하면 다양한 문제를 효과적으로 해결할 수 있습니다.
댓글