[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search) 알고리즘

깊이 우선 탐색 알고리즘이란?

깊이 우선 탐색 알고리즘 특징

• 메모리 효율성: 스택을 이용하기 때문에 노드 수에 비해 메모리 사용이 적음

• 깊이 우선: 시작점에서 멀리 떨어진 노드를 먼저 탐색하므로, 길이 긴 경로를 선호할 때 유리

• 트리 구조에서의 용도: DFS는 이진 트리의 순회(전위, 중위, 후위)에 자주 사용

깊이 우선 탐색 알고리즘 실제 적용 사례

• 미로 찾기: DFS는 한 경로를 끝까지 탐색한 후 다른 경로를 시도하기 때문에 미로를 탐색하는 데 유용

• 강한 연결 요소 찾기: 그래프에서 강하게 연결된 컴포넌트를 찾을 때

• 백트래킹 문제: N-퀸 문제와 같은 백트래킹 문제는 DFS를 기반으로 구현

깊이 우선 탐색 알고리즘의 단계

깊이 우선 탐색 구현 (ex. python)

### 입력 ###

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs(graph, 'A')

### 출력 ###
A B D E F C