로고

깊이 우선 탐색(DFS)이란? DFS 알고리즘 생각보다 어렵지 않아요

작성일 :

깊이 우선 탐색(DFS)이란?

깊이 우선 탐색(Depth-First Search, DFS)은 그래프 탐색 알고리즘의 하나로, 트리나 그래프의 모든 정점을 방문하는 방법 중 하나입니다. DFS는 스택을 사용하여 현재 경로를 추적하고, 더 이상 탐색할 정점이 없을 때까지 한 경로를 따라 깊이 들어가는 방식으로 작동합니다. 이 글에서는 DFS의 기본 개념, 구현 방법, 응용 사례, 그리고 장단점에 대해 자세히 설명하겠습니다.

1. 깊이 우선 탐색의 기본 개념

DFS는 시작 정점에서 출발하여 한 정점에서 다른 정점으로 최대한 깊숙이 들어간 후, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색하는 방식입니다. 이를 반복하여 모든 정점을 방문하게 됩니다. DFS는 주로 다음과 같은 단계로 구성됩니다:

  1. 시작 정점 선택: 탐색을 시작할 정점을 선택합니다.
  2. 방문 표시: 현재 정점을 방문했다고 표시합니다.
  3. 깊이 탐색: 인접한 정점 중 아직 방문하지 않은 정점이 있으면 그 정점으로 이동하여 탐색을 계속합니다.
  4. 백트래킹: 인접한 모든 정점을 방문했으면 이전 정점으로 돌아가 다른 경로를 탐색합니다.

2. 깊이 우선 탐색의 구현

DFS는 재귀와 비재귀(스택 사용) 두 가지 방법으로 구현할 수 있습니다. 여기서는 두 가지 방법 모두를 살펴보겠습니다.

재귀를 이용한 DFS 구현:

python
def dfs_recursive(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

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

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

# 방문 여부를 저장하는 리스트
visited = [False] * len(graph)

# DFS 호출
dfs_recursive(graph, 0, visited)

스택을 이용한 비재귀 DFS 구현:

python
def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()

        if not visited[v]:
            print(v, end=' ')
            visited[v] = True

            for neighbor in reversed(graph[v]):
                if not visited[neighbor]:
                    stack.append(neighbor)

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

# DFS 호출
dfs_stack(graph, 0)

3. 깊이 우선 탐색의 응용 사례

DFS는 다양한 문제 해결에 적용될 수 있습니다. 대표적인 응용 사례는 다음과 같습니다:

  • 경로 찾기: 특정 정점에서 다른 정점까지의 경로를 찾는 데 사용됩니다.
  • 사이클 탐지: 그래프 내에 사이클이 존재하는지 확인할 수 있습니다.
  • 위상 정렬: 방향 그래프의 위상 정렬을 수행하는 데 사용됩니다.
  • 강한 연결 요소: 방향 그래프에서 강한 연결 요소를 찾는 Kosaraju 또는 Tarjan 알고리즘의 일부로 사용됩니다.
  • 미로 탐색: 미로의 출구를 찾거나 모든 가능한 경로를 탐색하는 데 활용됩니다.

4. 깊이 우선 탐색의 장단점

DFS는 여러 가지 장점과 단점을 가지고 있습니다.

장점:

  • 메모리 효율성: DFS는 현재 경로만 저장하므로, 방문해야 할 정점이 많지 않다면 메모리 사용량이 적습니다.
  • 단순한 구현: 재귀 호출을 이용해 간단하게 구현할 수 있습니다.
  • 경로 탐색: 특정 경로를 찾는 데 매우 효과적입니다.

단점:

  • 깊이 제한 문제: 매우 깊은 그래프에서는 스택 오버플로우가 발생할 수 있습니다.
  • 비효율적 경로 탐색: 최단 경로를 찾는 데는 적합하지 않습니다. DFS는 모든 경로를 탐색하지 않기 때문입니다.
  • 무한 루프: 순환이 있는 그래프에서 방문을 추적하지 않으면 무한 루프에 빠질 수 있습니다.

5. 깊이 우선 탐색의 최적화

DFS의 성능을 최적화하려면 다음과 같은 기법을 사용할 수 있습니다:

  • 방문 확인 최적화: 방문 여부를 효율적으로 확인할 수 있는 데이터 구조를 사용합니다.
  • 모든 경로 탐색 방지: 특정 조건을 만족하는 경로를 찾으면 탐색을 중단하는 로직을 추가합니다.
  • 메모이제이션: 이미 계산한 경로를 저장하여 중복 계산을 방지합니다.

결론

깊이 우선 탐색(DFS)은 그래프 탐색에서 중요한 역할을 하는 알고리즘으로, 다양한 문제 해결에 사용될 수 있습니다. DFS는 단순한 구현과 효율적인 메모리 사용으로 인해 많은 응용 분야에서 사용되지만, 깊이 제한 문제와 비효율적 경로 탐색 등의 단점도 가지고 있습니다. 이 글에서 설명한 DFS의 개념과 구현, 응용 사례, 그리고 최적화 기법을 이해하면, 그래프 탐색 문제를 효과적으로 해결하는 데 도움이 될 것입니다.