Algorithm

[크래프톤 정글] DFS 개념 정리

하루이2222 2024. 9. 24. 20:51

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프나 트리 구조에서 노드를 탐색하거나 순회하는 알고리즘 중 하나다. 이 알고리즘은 가능한 한 깊이(즉, 자식 노드)를 먼저 탐색하는 것을 목표로 한다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 쉽게 구현할 수 있다.

1. DFS의 기본 원리

DFS는 시작 노드에서 시작하여 다음 노드를 방문할 때마다 깊이(자식 노드)로 최대한 내려간다. 더 이상 내려갈 수 없는 노드에 도달하면, 직전에 방문한 노드로 돌아와서 탐색하지 않은 다른 자식 노드를 탐색한다. 이 과정은 모든 노드를 방문할 때까지 계속된다.

2. DFS 구현 방법

DFS는 재귀 방식과 비재귀(반복문과 스택 사용) 방식으로 구현할 수 있다.

3. DFS의 특징

  • 완전 탐색: DFS는 모든 노드를 한 번씩 방문한다.
  • 경로 탐색: DFS는 한 번의 탐색 과정에서 시작 노드에서 목표 노드까지의 경로를 찾을 수 있다.
  • 스택 사용: 재귀적으로 호출할 경우, 함수 호출 스택이 내재적으로 사용되며, 명시적인 스택을 사용해서 반복문으로도 구현할 수 있다.
  • 백트래킹: DFS는 탐색 과정에서 더 이상 진행할 수 없을 때 이전 상태로 돌아가서 탐색을 계속한다. 이 백트래킹(backtracking) 과정이 중요한 특징이다.

4. DFS의 시간 복잡도

  • 시간 복잡도: DFS의 시간 복잡도는 그래프의 노드 수를 V, 간선 수를 E라고 할 때, O(V + E)이다. 이 복잡도는 그래프의 모든 노드와 간선을 한 번씩 방문하는 데 소요되는 시간에 해당한다.
  • 공간 복잡도: DFS의 공간 복잡도는 O(V)이며, 재귀 호출의 경우 함수 호출 스택에 의해 공간이 추가적으로 필요하다.

5. DFS의 응용

  • 경로 찾기: DFS는 특정 노드에서 다른 노드까지의 경로를 찾는 데 유용하다.
  • 사이클 탐지: DFS를 사용하여 그래프 내의 사이클을 탐지할 수 있다. 사이클이 있는 경우, 이미 방문한 노드를 다시 방문하게 된다.
  • 강한 연결 요소: DFS는 방향성 그래프에서 강한 연결 요소(SCC, Strongly Connected Components)를 찾는 Kosaraju's 알고리즘 등에 사용된다.
  • 탐색 문제: 미로 찾기와 같은 탐색 문제에서 가능한 경로를 모두 탐색하고자 할 때 DFS가 사용된다.

6. DFS의 한계 및 주의사항

  • 무한 루프: DFS는 무한히 깊어질 수 있는 그래프(예: 순환 구조를 가진 그래프)에서, 방문한 노드를 추적하지 않으면 무한 루프에 빠질 수 있다.
  • 메모리 사용: 트리의 깊이가 깊을 경우 재귀 호출이 많아져 스택 오버플로우(stack overflow)가 발생할 수 있다.
  • 최단 경로 탐색에 부적합: DFS는 최단 경로를 보장하지 않기 때문에, 최단 경로 탐색을 위해서는 BFS(Breadth-First Search)와 같은 다른 알고리즘을 사용하는 것이 적합하다.

DFS(Depth-First Search)의 동작 순서를 자세히 설명하면 다음과 같다.

1. 초기 설정

  • 그래프 정의: 탐색할 그래프는 노드(Node)와 간선(Edge)으로 이루어져 있다. 예를 들어, 그래프는 인접 리스트(adjacent list)나 인접 행렬(adjacent matrix)로 표현할 수 있다.
  • 방문 여부 확인을 위한 자료 구조: 그래프 탐색 중 이미 방문한 노드를 추적하기 위해 visited라는 집합(set)이나 배열을 사용한다. 이는 중복 방문을 방지하고, 무한 루프를 피하기 위함이다.
  • 스택(Stack): DFS는 LIFO(Last In, First Out) 원칙을 따르는 스택 자료 구조를 사용하여 탐색 순서를 관리한다. 재귀를 사용하는 경우, 함수 호출 스택이 이 역할을 한다.

2. 탐색 시작

  • 시작 노드 선택: 탐색을 시작할 첫 번째 노드를 선택한다. 이 노드는 그래프 내의 임의의 노드가 될 수 있다. 시작 노드는 스택에 넣고, 방문으로 표시한다.

3. 메인 탐색 루프

탐색은 스택이 빌 때까지, 혹은 모든 노드를 방문할 때까지 반복된다.

(1) 스택에서 노드 꺼내기

  • 스택에서 노드를 꺼낸다. 이 노드는 현재 탐색할 노드이다. 재귀적으로 구현된 경우에는 현재 함수 호출 스택의 최상단 노드가 된다.

(2) 노드 처리

  • 현재 노드에서 원하는 작업을 수행한다. 예를 들어, 노드 값을 출력하거나, 특정 조건을 확인할 수 있다.

(3) 인접 노드 탐색

  • 현재 노드에 인접한 모든 노드(자식 노드들)를 확인한다.
  • 각 인접 노드에 대해, 아직 방문하지 않은 노드라면:
    • 그 노드를 스택에 추가한다.
    • 해당 노드를 방문했다고 표시한다(visited에 추가).
    • 스택에 추가한 후, 스택에서 이 노드가 다시 꺼내질 때까지 탐색은 현재 노드에 대한 처리를 계속 진행한다.
    • 재귀적 구현에서는 이 과정이 함수 호출에 해당하며, 현재 노드의 처리가 완료될 때까지 다음 함수 호출로 넘어가지 않는다.

4. 백트래킹

  • 현재 노드에서 더 이상 방문할 수 있는 인접 노드가 없다면, 스택에서 이전 노드로 돌아간다. 이 과정은 "백트래킹"이라고 하며, 이전 단계로 돌아가서 아직 탐색하지 않은 다른 경로를 찾는다.
  • 이 과정은 스택이 빌 때까지 계속된다. 스택이 비었다는 것은 모든 가능한 경로를 다 탐색했음을 의미한다.

5. 탐색 종료

  • 모든 노드를 방문하거나, 탐색 조건을 만족하여 탐색을 종료한다.
  • 스택이 비어 있는 상태로 반복이 끝나면, DFS 탐색이 완료된다.

DFS 동작 예시

탐색할 그래프가 준비된다. 그래프는 각 노드와 그 노드에 연결된 이웃(인접) 노드들로 구성된다.

A - B - D
|   |
C   E

그래프의 인접 리스트 표현은 다음과 같다:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A'],
    'D': ['B'],
    'E': ['B']
}

2. 초기 설정

  • 스택 초기화: 탐색을 시작할 노드를 스택에 넣는다. 예를 들어, 시작 노드를 'A'로 선택한다.
  • 방문 집합 초기화: 방문한 노드를 추적하기 위해 빈 집합 visited를 준비한다.
stack = ['A']  # 시작 노드를 스택에 추가
visited = set()  # 방문한 노드를 기록할 집합

3. 탐색 시작

스택이 빌 때까지 다음 과정을 반복한다:

1) 스택에서 노드를 꺼낸다.

스택의 맨 위에 있는 노드를 꺼내어 현재 탐색 중인 노드로 설정한다. 예를 들어, 처음에는 'A'가 스택에서 꺼내진다.

node = stack.pop()  # 스택에서 노드 꺼내기

2) 노드를 방문 처리하고 작업을 수행한다.

현재 노드를 방문했음을 기록하고, 필요한 작업을 수행한다. 여기서는 단순히 노드 이름을 출력한다고 가정하겠다.

if node not in visited:
    visited.add(node)  # 노드를 방문했다고 표시
    print(node)  # 노드 출력 (또는 다른 작업 수행)

3) 현재 노드의 인접 노드를 스택에 추가한다.

현재 노드에 연결된(인접한) 다른 노드들을 확인하고, 방문하지 않은 노드만 스택에 추가한다.

for neighbor in graph[node]:
    if neighbor not in visited:
        stack.append(neighbor)  # 인접 노드를 스택에 추가

4. 과정 반복

이 과정을 스택이 빌 때까지 반복한다. 전체 과정을 예시 그래프로 추적하면 다음과 같다:

초기 상태:

  • 스택: ['A']
  • 방문: {}

1차 반복:

  • 스택에서 'A'를 꺼내고 방문: visited = {'A'}
  • 인접 노드 'B', 'C'를 스택에 추가: stack = ['B', 'C']

2차 반복:

  • 스택에서 'C'를 꺼내고 방문: visited = {'A', 'C'}
  • 'C'의 인접 노드는 'A'이지만 이미 방문했으므로 무시.
  • 스택 상태: ['B']

3차 반복:

  • 스택에서 'B'를 꺼내고 방문: visited = {'A', 'B', 'C'}
  • 인접 노드 'D', 'E'를 스택에 추가: stack = ['D', 'E']

4차 반복:

  • 스택에서 'E'를 꺼내고 방문: visited = {'A', 'B', 'C', 'E'}
  • 'E'의 인접 노드는 'B'이지만 이미 방문했으므로 무시.
  • 스택 상태: ['D']

5차 반복:

  • 스택에서 'D'를 꺼내고 방문: visited = {'A', 'B', 'C', 'D', 'E'}
  • 'D'의 인접 노드는 'B'이지만 이미 방문했으므로 무시.
  • 스택 상태: [] (스택이 비었으므로 탐색 종료)

5. 탐색 완료

모든 노드를 방문하고 스택이 비어 더 이상 탐색할 노드가 없으면 DFS 탐색이 종료된다. 탐색한 노드의 순서는 A -> C -> B -> E -> D가 된다.

요약

  1. 시작 노드를 스택에 넣는다.
  2. 스택에서 노드를 꺼낸다.
  3. 노드를 방문했다고 기록하고, 작업을 수행한다.
  4. 현재 노드의 인접 노드를 스택에 추가한다.
  5. 스택이 빌 때까지 2~4 단계를 반복한다.

이 과정을 통해 DFS는 그래프의 깊이부터 먼저 탐색하며, 가능한 모든 경로를 탐색할 때까지 탐색을 이어나간다.

구현

stack 을 이용한 반복적 구현

def dfs_iterative(graph, start):
    visited = set()  # 방문한 노드를 추적하는 집합
    stack = [start]  # 스택에 시작 노드를 넣음

    while stack:
        node = stack.pop()  # 스택에서 노드를 꺼냄
        if node not in visited:
            visited.add(node)  # 노드를 방문 처리
            print(node)  # 또는 원하는 작업 수행

            # 인접한 노드를 스택에 추가
            for neighbor in graph[node]:
                if neighbor not in visited:
                    stack.append(neighbor)

재귀를 활용한 구현

def dfs_recursive(graph, node, visited):
    # 현재 노드를 방문 처리
    visited.add(node)
    print(node)  # 또는 원하는 작업 수행

    # 인접한 노드들을 재귀적으로 방문
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)