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

🔹 DFS란?

1. 깊이 우선 탐색(Depth-First Search, DFS)의 정의

깊이 우선 탐색(Depth-First Search, DFS)은 그래프를 탐색하는 알고리즘으로, 한 경로를 끝까지 탐색한 후 다시 돌아가 다른 경로를 탐색하는 방식입니다. DFS는 스택(Stack) 또는 재귀(Recursion)를 활용하여 구현되며, 미로 탐색, 경로 찾기, 백트래킹 등에 널리 활용됩니다.

✅ DFS의 주요 특징:

• 한 경로를 끝까지 탐색한 후, 더 이상 진행할 수 없으면 이전 노드로 돌아감(백트래킹)
• 재귀 함수(Recursion) 또는 명시적 스택(Stack)을 사용하여 구현 가능
• BFS(너비 우선 탐색)와 달리 특정 경로를 먼저 탐색하는 방식
• O(V+E)의 시간 복잡도를 가짐 (V: 정점 수, E: 간선 수)

📌 DFS는 경로 탐색, 순열 및 조합 생성, 퍼즐 해결 등에 효과적으로 사용됩니다.

---

🔹 DFS의 주요 유형

1. 재귀(Recursion) 기반 DFS

✅ 재귀 호출을 사용하여 깊이 우선 탐색을 수행하는 방법

✔️ 재귀 DFS 예제 (Python):

def dfs_recursive(graph, node, visited):
    if node not in visited:
        visited.add(node)
        print(node, end=' ')
        for neighbor in graph[node]:
            dfs_recursive(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
visited = set()
dfs_recursive(graph, 'A', visited)  # 출력: A B D E F C

📌 재귀 기반 DFS는 코드가 간결하지만, 깊이가 깊어질 경우 스택 오버플로우(Stack Overflow) 위험이 있습니다.

2. 스택(Stack) 기반 DFS

✅ 명시적인 스택 자료구조를 사용하여 DFS를 구현하는 방법

✔️ 스택 기반 DFS 예제 (Python):

def dfs_stack(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node, end=' ')
            stack.extend(reversed(graph[node]))

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
dfs_stack(graph, 'A')  # 출력: A C F E B D

📌 스택을 활용하면 재귀 호출의 한계를 극복할 수 있으며, 깊이가 깊은 그래프에서도 활용 가능합니다.

---

🔹 DFS vs BFS 비교

비교 항목	깊이 우선 탐색(DFS)	너비 우선 탐색(BFS)
탐색 방식	한 경로를 끝까지 탐색한 후 백트래킹	가장 가까운 노드부터 탐색
구현 방식	스택(Stack) 또는 재귀(Recursion)	큐(Queue) 사용
최단 경로	최단 경로 보장 X	최단 경로 보장 O (비가중 그래프)
시간 복잡도	O(V+E)	O(V+E)
공간 복잡도	O(V) (재귀 깊이에 따라 증가)	O(V) (큐 크기에 따라 증가)

📌 DFS는 백트래킹 문제에 적합하며, BFS는 최단 경로 탐색에 적합합니다.

---

🔹 DFS의 활용 사례

1. 경로 탐색(Path Finding)

✅ 미로 문제, 게임 AI에서 길 찾기 알고리즘으로 활용됨

✔️ 미로 탐색 예제:

def find_path(maze, start, end, path=[]):
    x, y = start
    if start == end:
        return path + [end]
    for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:
        next_pos = (x+dx, y+dy)
        if next_pos in maze and next_pos not in path:
            new_path = find_path(maze, next_pos, end, path + [start])
            if new_path:
                return new_path
    return None

maze = {(0,0), (0,1), (1,1), (2,1), (2,2), (3,2)}
print(find_path(maze, (0,0), (3,2)))  # 출력: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (3, 2)]

📌 DFS를 활용하면 미로 같은 복잡한 환경에서도 경로를 탐색할 수 있습니다.

2. 순열 및 조합 생성(Backtracking)

✅ 백트래킹을 활용한 조합 및 순열 생성

✔️ 순열 생성 예제:

def permutations(arr, path=[]):
    if not arr:
        print(path)
    for i in range(len(arr)):
        permutations(arr[:i] + arr[i+1:], path + [arr[i]])

permutations([1, 2, 3])

📌 DFS는 조합 및 순열을 구하는 문제에서 필수적으로 사용됩니다.

3. 강결합 요소(SCC) 찾기 (타잔 알고리즘)

✅ 방향 그래프에서 강하게 연결된 요소를 찾는 알고리즘

📌 SNS 친구 추천 시스템, 웹페이지 링크 분석에 사용됩니다.

---

📌 결론

✅ 깊이 우선 탐색(DFS)은 그래프 탐색에서 가장 널리 사용되는 알고리즘 중 하나입니다.
✅ 스택 또는 재귀를 활용하여 구현 가능하며, 백트래킹, 미로 탐색, 경로 찾기 등에 유용합니다.
✅ BFS와 비교하여 특정한 문제(경로 탐색, 순열 생성)에 적합한 선택지가 됩니다.
✅ 재귀 호출이 깊어질 경우 스택 오버플로우를 방지하기 위해 스택 기반 DFS를 사용할 수 있습니다.