DFS 알고리즘 (Depth First Search)

1. DFS 알고리즘의 개념과 작동 방식

DFS (Depth First Search) 알고리즘은 그래프를 탐색하는 방법 중 하나로, 현재 정점에서 더 이상 갈 수 있는 정점이 없을 때까지 깊이 우선으로 탐색하여 모든 정점을 방문하는 알고리즘입니다. DFS는 스택 또는 재귀 함수를 이용하여 구현할 수 있습니다.

DFS 알고리즘은 다음과 같은 작동 방식을 갖습니다:

1. 시작 정점을 방문하고, 해당 정점을 스택에 넣습니다.
2. 스택이 비어 있지 않을 동안 다음을 반복합니다:
   1. 스택의 가장 위에 있는 정점을 꺼내어 현재 정점으로 설정합니다.
   2. 현재 정점과 인접한 정점 중 아직 방문하지 않은 정점이 있다면, 해당 정점을 방문하고 스택에 넣습니다.
   3. 모든 인접한 정점을 방문한 경우, 스택에서 현재 정점을 삭제합니다.
3. 스택이 비어있으면 모든 정점을 방문한 것입니다.

DFS 알고리즘은 스택을 이용하기 때문에, 가장 마지막에 넣은 정점을 먼저 처리하므로 깊이 우선으로 탐색하는 특징을 가지게 됩니다. 이러한 탐색 방식으로 인해, 한 정점에서 인접한 정점으로 최대한 깊게 탐색하게 됩니다.

2. DFS 알고리즘의 응용 사례

DFS 알고리즘은 그래프 탐색에 주로 사용되며, 다양한 응용 사례가 있습니다. 몇 가지 대표적인 응용 사례는 다음과 같습니다:

1. 그래프 순회: DFS는 그래프의 모든 정점을 탐색하는데 사용됩니다. 그래프가 연결되어 있을 때, DFS를 사용하여 모든 정점을 방문하고 연결된 모든 경로를 탐색할 수 있습니다.

2. 미로 찾기: DFS 알고리즘은 미로에서 가장 빠른 경로를 찾는데 사용될 수 있습니다. 시작점부터 DFS를 이용해 갈 수 있는 경로를 탐색하다가 도착점에 도달하면 탐색을 종료하고 최단 경로를 얻을 수 있습니다.

3. 서로 연결된 구성 요소 찾기: 그래프에서 서로 연결된 구성 요소를 찾는데 DFS를 사용할 수 있습니다. 시작점에서 DFS를 수행하여 해당 구성 요소에 속하는 모든 정점을 방문할 수 있습니다.

4. 위상 정렬: DFS 알고리즘을 사용하여 방향 그래프의 정점들을 위상 순서로 나열하는 위상 정렬을 구현할 수 있습니다. 이를 활용하여 우선순위 작업의 실행 순서를 결정할 수 있습니다.

5. 사이클 탐지: DFS를 사용하여 그래프에서 사이클을 탐지할 수 있습니다. 정점을 방문하는 과정에서 이미 방문한 정점을 만나면 사이클이 존재하는 것으로 판단할 수 있습니다. 사이클을 탐지하는 것은 그래프의 유효성을 검사하는데 유용합니다.

이 외에도 DFS는 그래프 문제뿐만 아니라 미로 게임, 재귀적인 문제 해결 등 다양한 알고리즘 문제에서 활용될 수 있습니다. DFS는 그래프 구조에 따라 깊이 우선으로 탐색하는 특징을 가지고 있기 때문에, 탐색 문제뿐만 아니라 여러 종류의 문제에 적용할 수 있습니다.

3. DFS 알고리즘의 장단점

DFS 알고리즘은 다음과 같은 장점과 단점을 갖습니다.

장점:

• 구현이 간단하며, 스택 또는 재귀 함수를 이용하여 구현할 수 있습니다. 이로 인해 코드가 간결하고 직관적입니다.

• 깊이 우선 탐색이기 때문에, 시작점으로부터 최대한 깊게 탐색하기 때문에 가능한 빠르게 해답에 도달할 수 있습니다. 따라서, 최단 경로 찾기와 같은 문제에 적합합니다.

단점:

• 그래프가 무한히 깊어질 수 있는 경우, 탐색이 끝나지 않을 수 있습니다. 따라서, 메모리 문제가 발생할 수 있습니다.

• BFS보다 특정 경로를 찾기 어려울 수 있습니다. DFS는 한 번에 하나의 경로를 탐색하기 때문에, 답이 될 수 있는 모든 경로를 탐색하기 위해 전체 그래프를 탐색해야 할 수도 있습니다.

• DFS는 백트래킹을 사용하는 경우에 효과적이지만, 최적화 문제에는 적합하지 않을 수 있습니다. 최적화 문제에서는 모든 가능한 경로를 탐색하는 대신 특정 기준에 따라 가장 좋은 경로를 선택하는 것이 중요합니다.

• DFS는 깊이 우선으로 탐색하기 때문에, 동일한 정점을 반복해서 방문할 수 있습니다. 이러한 반복 방문을 방지하기 위해 방문한 정점을 체크하는 것이 필요합니다.

DFS는 구현이 간단하고, 최단 경로 찾기 등 깊이 우선 탐색에 적합한 문제에서 효과적입니다. 그러나 무한 깊이의 그래프와 같이 탐색이 끝나지 않을 수 있는 경우나 최적화 문제에는 제한적일 수 있습니다. 이러한 장단점을 고려하여 DFS 알고리즘을 적합한 문제에 적용해야 합니다.

4. DFS 알고리즘의 시간 복잡도와 공간 복잡도

DFS 알고리즘의 시간 복잡도와 공간 복잡도는 다음과 같습니다.

시간 복잡도:

DFS는 그래프의 모든 정점을 한 번씩 방문하는데 시간이 걸립니다. 따라서, 그래프의 모든 정점을 탐색하기 위한 시간 복잡도는 O(V) 입니다. 여기서 V는 정점의 개수입니다.

또한, DFS는 각 정점에서 인접한 모든 정점을 방문하기 위해 인접한 간선을 모두 탐색합니다. 따라서, 인접한 정점을 탐색하는데 걸리는 시간은 해당 정점의 차수에 비례합니다. 만약, 그래프가 인접 리스트로 표현되어 있다면, 각 정점에서 인접한 정점을 탐색하는데 O(1)의 시간이 걸리며, 그래프의 모든 간선을 탐색해야 하므로 O(E)의 시간이 소요됩니다. 여기서 E는 간선의 개수입니다.

따라서, DFS 알고리즘의 최종 시간 복잡도는 O(V + E)입니다.

공간 복잡도:

DFS 알고리즘에서 사용되는 가장 중요한 자료 구조는 스택 또는 재귀 함수의 호출 스택입니다. DFS는 시작 정점부터 탐색을 시작하고, 인접한 정점을 계속해서 스택에 추가하면서 탐색을 진행합니다. 따라서, 스택에는 최악의 경우 정점의 개수만큼의 요소가 저장될 수 있습니다. 이는 그래프의 깊이에 따라 달라지며, 최악의 경우 무한히 깊어진다면 스택의 크기는 무한히 커질 수 있습니다.

또한, DFS는 방문 여부를 체크하기 위한 배열이나 리스트를 사용합니다. 이 배열은 그래프의 정점 개수에 비례하며, 모든 정점을 방문하고 체크하기 위해서는 O(V)의 공간이 필요합니다.

따라서, DFS 알고리즘의 최종 공간 복잡도는 O(V)입니다. 다만, 최악의 경우 스택이 무한히 커진다면 공간 복잡도는 O(∞)이 될 수 있습니다.

5. DFS 알고리즘의 구현 방법과 주요 코드 예시

DFS 알고리즘은 스택 또는 재귀 함수를 이용하여 구현할 수 있습니다. 여기서는 재귀 함수를 이용한 구현 방법에 대해 설명하고, 주요 코드 예시를 제시하겠습니다.

재귀 함수를 이용한 구현 방법:

1. 시작 정점을 방문하고, 방문한 정점을 체크합니다.

2. 현재 정점과 인접한 정점 중에서 방문하지 않은 정점을 재귀적으로 탐색합니다. 이때, 탐색한 정점은 방문한 정점으로 체크합니다.

3. 모든 인접한 정점을 탐색한 후에는 백트래킹을 수행합니다. 즉, 현재 정점의 탐색을 종료하고 이전 정점으로 돌아갑니다.

4. 시작 정점으로부터 탐색을 시작하여 모든 정점을 방문할 때까지 2-3단계를 반복합니다.

주요 코드 예시:

다음은 재귀 함수를 이용한 DFS 알고리즘의 주요 코드 예시입니다. 이 예시에서는 인접 리스트로 표현된 그래프를 기준으로 설명합니다.

def dfs(vertex, visited, graph):
    # 현재 정점 방문
    visited[vertex] = True
    print(vertex, end=' ')

    # 현재 정점과 인접한 정점들에 대해 재귀 호출
    for adjacent_vertex in graph[vertex]:
        if not visited[adjacent_vertex]:
            dfs(adjacent_vertex, visited, graph)

# 그래프 정보
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3]
}

# 정점의 개수
num_vertices = len(graph)

# 방문 여부를 체크하기 위한 배열
visited = [False] * (num_vertices + 1)

# DFS 호출
dfs(1, visited, graph)

위의 코드 예시에서는 dfs 함수를 정의하여 DFS 알고리즘을 구현하였습니다.

• 첫 번째 인자인 vertex는 현재 탐색하는 정점을 의미합니다.
• 두 번째 인자인 visited는 방문 여부를 체크하기 위한 배열로, 정점의 개수보다 하나 더 크게 할당합니다.
• 세 번째 인자인 graph는 인접 리스트 형태의 그래프 정보를 나타냅니다.

dfs 함수에서는 현재 정점을 방문하고 체크한 뒤, 인접한 정점을 재귀적으로 탐색합니다. 이때, 방문하지 않은 정점에 대해서만 탐색을 진행합니다. 그리고 각 정점을 탐색한 후에는 백트래킹을 수행하여 이전 정점으로 돌아갑니다.

위의 코드 예시를 실행하면, 시작 정점에서부터 DFS 탐색을 시작하여 그래프의 모든 정점을 방문하는 순서대로 출력됩니다.