Python 코딩테스트 03: DFS

깊이 우선 탐색(DFS) 알고리즘: 이해와 응용

DFS (Depth-First Search) 이해와 응용

개요

DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다.

이 알고리즘은 한 노드를 시작점으로 깊이 들어가며 탐색하다가 더 이상 갈 수 없으면 돌아와 다른 경로를 탐색하는 방식입니다.

DFS는 주로 경로 찾기, 사이클 탐지, 연결 요소 찾기 등의 문제에서 유용하게 사용됩니다.

이번 포스팅에서는 DFS의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다.

 

DFS의 원리

DFS는 다음과 같은 단계로 진행됩니다:

1. 초기화: 탐색을 시작할 노드를 스택(stack)에 추가하고 방문 표시를 합니다.
2. 탐색: 스택에서 노드를 꺼내어 해당 노드의 인접한 노드들을 모두 스택에 추가합니다. 이때, 방문하지 않은 노드만 스택에 추가하고 방문 표시를 합니다.
3. 반복: 스택이 빌 때까지 2단계를 반복합니다.

DFS는 스택을 사용하여 구현하며, 재귀를 이용하여 구현할 수도 있습니다.

한 경로를 끝까지 탐색한 후 다른 경로로 이동하므로, 트리 구조에서 깊이 우선 탐색을 수행할 때 매우 유용합니다.

 

DFS의 단계별 예시

예시 그래프

다음과 같은 그래프가 있다고 가정해봅시다:

A - B - D
|   |
C - E

이 그래프에서 A 노드를 시작점으로 DFS를 수행해보겠습니다.

1. 스택에 A를 추가하고 방문 표시합니다. 스택: [A] 방문: {A}
2. 스택에서 A를 꺼내고 인접한 노드 B, C를 스택에 추가합니다. 스택: [B, C] 방문: {A, B, C}
3. 스택에서 C를 꺼내고, C의 인접한 노드 B는 이미 방문했으므로 추가하지 않습니다. 스택: [B] 방문: {A, B, C}
4. 스택에서 B를 꺼내고 인접한 노드 D, E를 스택에 추가합니다. 스택: [D, E] 방문: {A, B, C, D, E}
5. 스택에서 E를 꺼내고, E의 인접한 노드 B, C는 이미 방문했으므로 추가하지 않습니다. 스택: [D] 방문: {A, B, C, D, E}
6. 스택에서 D를 꺼내고, D의 인접한 노드 B는 이미 방문했으므로 추가하지 않습니다. 스택: [] 방문: {A, B, C, D, E}

스택이 비었으므로 DFS가 종료됩니다.

 

그림으로 보는 DFS

Initial Graph:
A - B - D
|   |
C - E

DFS Traversal:
1. Start at A: Stack = [A], Visited = {A}
2. Visit B, C: Stack = [B, C], Visited = {A, B, C}
3. Continue with B: Stack = [D, E], Visited = {A, B, C, D, E}
4. Continue with remaining nodes: Stack = [], Visited = {A, B, C, D, E}

 

DFS의 구현

DFS는 주로 스택 자료구조를 사용하여 구현하며, 재귀를 이용하여 구현할 수도 있습니다.

DFS 코드 예시

반복적 구현 (스택 사용)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            stack.extend(reversed(graph[node]))  # 인접 노드를 스택에 추가

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

# 예시 실행
dfs_iterative(graph, 'A')
# 출력: A B D E C

 

재귀적 구현

def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node, end=' ')

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

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

# 예시 실행
dfs_recursive(graph, 'A')
# 출력: A B D E C

 

DFS의 특징

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 공간 복잡도: O(V) (스택이나 재귀 호출 스택에 최대 V개의 노드가 저장될 수 있음)
• 용도: 경로 찾기, 사이클 탐지, 연결 요소 찾기 등

 

DFS의 활용

DFS는 다양한 문제에서 활용될 수 있습니다.

경로 찾기

DFS는 그래프에서 특정 노드로 가는 경로를 찾는 데 유용합니다. 재귀 호출을 이용하여 시작점에서 목표 지점까지의 경로를 쉽게 찾을 수 있습니다.

사이클 탐지

DFS를 이용하여 그래프에서 사이클을 탐지할 수 있습니다. 탐색 중에 방문한 노드를 다시 방문하게 되면 사이클이 존재하는 것입니다.

연결 요소 찾기

DFS를 이용하여 그래프에서 연결 요소를 찾을 수 있습니다. 모든 노드를 방문하면서 연결 요소를 확인하고 각 요소를 별도로 탐색합니다.

 

예제: 미로 탐색

다음은 DFS를 사용하여 미로를 탐색하는 예제입니다.

def dfs_maze(maze, start, end):
    stack = [start]
    visited = set()
    path = []

    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        path.append(node)

        if node == end:
            return path

        x, y = node
        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            next_node = (x + dx, y + dy)
            if 0 <= next_node[0] < len(maze) and 0 <= next_node[1] < len(maze[0]) and maze[next_node[0]][next_node[1]] == 0:
                stack.append(next_node)
    return None

# 예시 미로
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

# 예시 실행
start = (0, 0)
end = (4, 4)
path = dfs_maze(maze, start, end)
print(path)
# 출력: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (4, 2), (4, 3), (4, 4)]

 

결론

DFS는 그래프나 트리 탐색에서 널리 사용되는 알고리즘입니다.

깊이 우선 탐색을 통해 한 경로를 끝까지 탐색하고, 돌아와 다른 경로를 탐색하는 방식으로 작동합니다.

DFS의 원리를 이해하고 다양한 문제에 적용하는 연습을 통해 효율적인 문제 해결 능력을 기를 수 있습니다.