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

깊이 우선 탐색(DFS, Depth-First Search) 알고리즘은 그래프 또는 트리의 노드를 탐색하는 데 사용되는 기본적인 알고리즘입니다. DFS는 한 방향으로 가능한 깊게 탐색한 후, 더 이상 갈 수 없게 되면 마지막 분기점으로 되돌아가서 다른 경로를 탐색하는 방식으로 작동합니다.

 

 

동작 원리

1. 시작 노드 선택: 탐색을 시작할 노드를 선택합니다. 일반적으로 루트 노드나 시작 지점이 됩니다.
2. 탐색: 현재 노드를 방문하고, 그 노드와 연결된 인접 노드 중 방문하지 않은 노드를 선택하여 탐색을 계속합니다.
3. 재귀적 호출: 방문한 노드에서 인접한 노드를 재귀적으로 탐색합니다.
4. 백트래킹: 더 이상 방문할 노드가 없으면 이전 노드로 되돌아가 다른 인접 노드를 탐색합니다.
5. 종료 조건: 모든 노드를 탐색할 때까지 이 과정을 반복합니다.

---

구현 방법

DFS는 두 가지 주요 방법으로 구현할 수 있습니다:

• 재귀(Recursive) 방식
• 스택(Stack) 사용: 명시적으로 스택을 사용하여 DFS를 구현할 수 있습니다.

 

1. 재귀적 구현

def dfs(graph, node, visited):
    if node not in visited:
        print(node)  # 노드 방문
        visited.add(node)  # 방문한 노드 기록
        for neighbor in graph[node]:  # 인접 노드 탐색
            dfs_recursive(graph, neighbor, visited)

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# DFS 호출
visited = set()
dfs(graph, 'A', visited)

 

2. 스택을 이용한 구현

def dfs(graph, start):
    visited = set()
    stack = [start]  # 시작 노드를 스택에 추가

    while stack:
        node = stack.pop()  # 스택의 가장 위 노드를 꺼냄
        if node not in visited:
            print(node)  # 노드 방문
            visited.add(node)  # 방문한 노드 기록
             for neighbor in graph[node][::-1]:  # 인접 노드를 역순으로 반복
                stack.append(neighbor)  # 스택에 추가

# 그래프 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# DFS 호출
dfs(graph, 'A')

 

---

 

DFS의 특징

• 장점:
  • 모든 노드를 탐색할 수 있으며, 특정 노드를 찾거나 경로를 확인하는 데 유용합니다.
  • 구현이 간단하고 직관적입니다.
• 단점:
  • 깊이가 깊은 그래프(예: 길게 늘어선 트리)에 대해 스택 오버플로우가 발생할 수 있습니다.
  • 최악의 경우(모든 노드를 탐색해야 하는 경우) 시간 복잡도가 O(V + E)입니다. 여기서 V는 정점 수, E는 간선 수입니다.