[Algorithm/알고리즘] DFS - 깊이 우선 탐색 알고리즘 이해하기

소개

깊이 우선 탐색(DFS)은 컴퓨터 과학에서 매우 중요한 알고리즘입니다. 트리나 그래프와 같은 자료 구조를 탐색하거나 검색하는 데 사용됩니다. DFS는 루트 노드에서 시작하여 가능한 한 깊이 내려가며 탐색한 후 되돌아옵니다. 이 게시물에서는 DFS의 기본 개념, 구현 방법, 응용 사례 및 예제 코드를 자세히 설명하겠습니다.

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

DFS는 그래프나 트리를 탐색하는 알고리즘입니다. 루트 노드에서 시작하여 각 분기를 가능한 한 깊이 탐색한 후 다시 되돌아옵니다. 이 방법은 먼저 깊숙이 탐색한 다음 형제 노드를 탐색하는 방식입니다.

DFS의 주요 특성

1. 스택 사용: DFS는 스택이라는 자료 구조를 사용합니다. 스택은 재귀를 통해 암시적으로 사용할 수도 있습니다.
2. 방문한 노드 기록: DFS는 사이클(순환)과 반복 방문을 방지하기 위해 방문한 노드를 기록합니다.
3. 경로 탐색: DFS는 각 경로를 가장 깊은 지점까지 탐색한 후 다음 경로로 이동합니다.

단계별 과정

1. 루트에서 시작: 루트 노드에서 시작합니다(그래프의 경우 임의의 노드에서 시작).
2. 노드 방문: 현재 노드를 방문했다고 표시합니다.
3. 인접 노드 탐색: 각 인접 노드에 대해 방문하지 않았다면 재귀적으로 DFS를 적용합니다.
4. 되돌아가기: 모든 인접 노드를 방문한 후 이전 노드로 되돌아갑니다.

DFS 구현

DFS는 두 가지 주요 방식으로 구현할 수 있습니다: 스택 사용과 재귀 사용입니다.

재귀적 구현

DFS를 재귀적으로 구현하면 코드는 간단해집니다. 함수가 자기 자신을 호출하여 깊이 탐색합니다.

def dfs_recursive(graph, node, visited):
    # 현재 노드가 방문되지 않은 경우
    if node not in visited:
        # 현재 노드를 출력
        print(node)
        # 현재 노드를 방문한 것으로 표시
        visited.add(node)
        # 현재 노드의 모든 인접 노드에 대해
        for neighbour in graph[node]:
            # 재귀적으로 DFS를 호출
            dfs_recursive(graph, neighbour, visited)

# 예제 사용:
graph = {
    'A' : ['B', 'C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
}

visited = set()  # 방문한 노드를 저장할 집합
dfs_recursive(graph, 'A', visited)  # DFS 시작

스택을 사용한 반복적 구현

스택을 사용하여 DFS를 반복적으로 구현할 수도 있습니다. 스택은 방문할 노드를 추적하는 데 사용됩니다.

def dfs_iterative(graph, start):
    visited = set()  # 방문한 노드를 저장할 집합
    stack = [start]  # 시작 노드를 스택에 추가
    
    while stack:  # 스택이 비어 있지 않은 동안
        node = stack.pop()  # 스택의 맨 위 노드를 꺼냄
        if node not in visited:  # 해당 노드를 아직 방문하지 않았다면
            print(node)  # 노드를 출력
            visited.add(node)  # 노드를 방문한 것으로 표시
            # 인접 노드를 스택에 추가 (역순으로 추가하여 올바른 순서로 처리)
            stack.extend(reversed(graph[node]))

# 예제 사용:
dfs_iterative(graph, 'A')  # DFS 시작

DFS의 응용

DFS는 여러 가지 유용한 응용 사례가 있습니다:

1. 경로 찾기: DFS는 그래프에서 두 노드 간의 경로를 찾는 데 사용할 수 있습니다.
2. 사이클 탐지: DFS는 그래프에서 사이클을 감지하는 데 도움이 됩니다.
3. 위상 정렬: 스케줄링 문제에서 DFS는 유향 비순환 그래프의 위상 정렬에 사용될 수 있습니다.
4. 퍼즐 해결: DFS는 미로, 스도쿠 등 모든 가능한 경로를 탐색하여 퍼즐을 해결할 수 있습니다.

장점과 단점

장점:

• 구현이 간단합니다.
• 간선이 적은 그래프에서 메모리를 효율적으로 사용합니다.

단점:

• 목표가 아닌 깊은 경로에서 멈출 수 있습니다(제한을 두거나 반복 깊이 우선 탐색을 사용할 수 있음).
• 최단 경로를 찾는 것이 보장되지 않습니다(BFS와는 다르게).

복잡도 분석

DFS의 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 최악의 경우 모든 정점과 간선을 탐색할 수 있기 때문입니다. 공간 복잡도는 그래프 표현 방식에 따라 다르며, 일반적으로 스택이나 재귀를 사용하기 때문에 O(V)입니다.

DFS 예제

이 예제 이미지는 DFS 알고리즘이 그래프를 탐색하는 과정을 단계별로 보여주고 있습니다. 그래프는 0부터 4까지의 노드로 구성되어 있으며, 이미지에서 화살표는 탐색 순서를 나타내고, 노드는 방문되면 노란색으로 표시됩니다.

단계별 설명

1. 노드 0에서 시작:
   • 탐색은 노드 0에서 시작하여, 해당 노드를 방문한 것으로 표시합니다.
2. 노드 1 방문:
   • 노드 0에서 인접한 노드 1로 이동하여 방문합니다.
3. 노드 0으로 되돌아가기:
   • 노드 1에 인접한 방문하지 않은 노드가 없으므로, 노드 0으로 되돌아갑니다.
4. 노드 2 방문:
   • 노드 0에서 인접한 노드 2로 이동하여 방문합니다.
5. 노드 3 방문:
   • 노드 2에서 인접한 노드 3으로 이동하여 방문합니다.
6. 노드 2로 되돌아가기:
   • 노드 3에 인접한 방문하지 않은 노드가 없으므로, 노드 2로 되돌아갑니다.
7. 노드 4 방문:
   • 노드 2에서 인접한 노드 4로 이동하여 방문합니다.
8. 노드 2, 그리고 노드 0으로 되돌아가기:
   • 노드 4에 인접한 방문하지 않은 노드가 없으므로, 노드 2로, 그 다음에 노드 0으로 되돌아갑니다.

DFS 구현 방법

다음은 이 과정을 Python으로 구현한 DFS 코드입니다. 이 코드는 그래프의 탐색 과정을 단계별로 보여줍니다.

def dfs(graph, start):
    visited = set()  # 방문한 노드를 기록하기 위한 집합
    
    def dfs_recursive(node):
        if node not in visited:
            print(node)  # 방문한 노드를 출력합니다
            visited.add(node)  # 노드를 방문한 것으로 표시합니다
            for neighbour in graph[node]:
                dfs_recursive(neighbour)  # 인접한 노드를 재귀적으로 방문합니다

    dfs_recursive(start)

# 그래프를 인접 리스트로 표현한 예제
graph = {
    0: [1, 2],
    1: [],
    2: [3, 4],
    3: [],
    4: []
}

# 노드 0에서 시작하여 DFS를 수행합니다
dfs(graph, 0)

단계별 실행 설명

1. 노드 0에서 시작:
   • 방문한 노드: {0}
2. 노드 1 방문:
   • 방문한 노드: {0, 1}
3. 노드 0으로 되돌아가기:
   • 재귀적으로 되돌아갑니다.
4. 노드 2 방문:
   • 방문한 노드: {0, 1, 2}
5. 노드 3 방문:
   • 방문한 노드: {0, 1, 2, 3}
6. 노드 2로 되돌아가기:
   • 재귀적으로 되돌아갑니다.
7. 노드 4 방문:
   • 방문한 노드: {0, 1, 2, 3, 4}
8. 노드 2, 그리고 노드 0으로 되돌아가기:
   • 재귀적으로 되돌아갑니다.

이 코드는 이미지에서 보여준 DFS 탐색 과정을 정확히 반영합니다. DFS는 스택을 사용하여 인접한 노드를 방문하고, 방문한 노드를 기록하여 반복 방문을 방지합니다. 이러한 방식을 통해 그래프의 모든 노드를 깊이 우선으로 탐색할 수 있습니다.

결론

깊이 우선 탐색(DFS)은 컴퓨터 과학자나 개발자의 도구 상자에서 다재다능하고 필수적인 알고리즘입니다. 깊이 지향적인 접근 방식은 단순한 경로 찾기에서 복잡한 문제 해결에 이르기까지 다양한 응용 분야에 적합합니다. DFS를 이해하고 구현하면 알고리즘적 사고와 문제 해결에 새로운 가능성을 열어줍니다.