깊이 우선 탐색 (DFS) 알고리즘

7.1 DFS 알고리즘의 작동 원리

깊이 우선 탐색 (Depth-First Search, DFS)는 그래프를 순회하거나 탐색하는 알고리즘이야. 시작 정점에서 시작해서 방문하지 않은 이웃이 없을 때까지 그래프를 더 깊이 탐색한 다음, 돌아가서 다른 정점으로 계속 진행해.

알고리즘 단계:

1. 선택한 시작 정점에서 시작하고, 방문한 것으로 표시해.
2. 첫 번째 방문하지 않은 이웃 정점을 탐색해.
3. 이 이웃 정점에 대해 단계 1과 2를 반복해.
4. 현재 정점의 이웃이 모두 방문되면 이전 정점으로 돌아가 (backtrack) 과정을 계속해.
5. 시작 정점에서 도달할 수 있는 모든 정점을 방문할 때까지 과정을 반복해.

시각화:

DFS의 시간 및 공간 복잡도:

시간 복잡도:

O(V + E), 여기서 V는 정점의 수, E는 간선의 수야.

그래프의 각 노드와 각 간선은 한 번씩 방문돼.

공간 복잡도:

O(V), 호출 스택이나 명시적 스택을 사용하여 정점을 저장하고, 상태 (방문한 정점)를 저장하기 위한 배열을 사용하기 때문이야.

7.2 재귀를 사용한 DFS 구현

먼저 재귀를 사용해서 DFS를 구현해보자 — 코드가 아름답고 간결할거야.

재귀적 DFS 구현:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 노드 처리
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# 사용 예시:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 스택을 사용한 DFS 구현

재귀 없이 구현하면 코드가 조금 더 길어져, 왜냐하면 방문한 정점의 목록을 추가로 저장해야 하거든.

스택을 사용한 반복적 DFS 구현:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 노드 처리
        
            for neighbor in reversed(graph[vertex]):  # 올바른 순회 순서를 위해 반대로 순회
                if neighbor not in visited:
                    stack.append(neighbor)
        
# 사용 예시:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 DFS를 사용해 해결할 수 있는 문제의 예

DFS를 사용하여 해결할 수 있는 고전적인 문제의 예:

1. 미로에서의 경로 찾기:

시작 지점에서 끝 지점까지 미로에서 경로를 찾는 데 사용돼.

적용 분야:

비디오 게임과 로봇공학에서 미로와 복잡한 공간을 탐색하는 데 사용돼.

2. 그래프 연결성 검사:

그래프가 연결되어 있는지 (모든 두 정점 사이에 경로가 있는지) 확인하는 것.

적용 분야:

네트워크 분석에서 네트워크 연결성을 검사하는 데 사용돼.

3. 위상 정렬:

방향성 비순환 그래프 (DAG)의 정점을 정렬하는 데 사용돼. 모든 간선 (u, v)에 대해 정점 u가 정점 v에 앞서도록.

적용 분야:

컴파일러에서 의존성과 작업을 정리하는 데 사용돼.

4. 그래프에서 사이클 발견:

그래프에 사이클이 있는지 검사하는 것.

적용 분야:

의존성 분석에서 순환 의존성을 발견하는 데 사용돼.

5. 미로 생성:

랜덤 미로를 생성하는 데 DFS 사용.

적용 분야:

게임 및 엔터테인먼트 애플리케이션에서 미로를 생성하는 데 사용돼.