개발이야기/파이썬

[알고리즘] DFS - 깊이우선 탐색

Study & Stack 2025. 6. 4. 00:51
728x90

DFS (Depth-First Search): 깊이 우선 탐색

DFS는 그래프 탐색 알고리즘의 하나로, 가능한 한 깊이 내려가면서 탐색하는 방식입니다. 특정 경로의 끝까지 도달한 후, 더 이상 갈 곳이 없으면 이전 노드로 되돌아와(백트래킹) 다른 경로를 탐색합니다. 마치 미로를 찾아 들어갈 때 한 길을 택해 끝까지 가보고, 막히면 되돌아 나와 다른 길을 찾는 것과 유사합니다.

1. 핵심 개념:

  • 백트래킹 (Backtracking): 한 경로를 끝까지 탐색하다가 더 이상 갈 수 있는 노드가 없으면, 이전에 방문했던 노드로 되돌아가(백트래킹) 다른 미탐색 경로를 찾아 다시 탐색을 이어갑니다.
  • 스택 (Stack) 자료구조 또는 재귀 (Recursion) 사용: DFS는 탐색 순서를 관리하기 위해 스택(Stack) 자료구조를 사용하거나, 스택의 원리와 동일한 재귀 함수 호출을 통해 구현됩니다. 스택은 '후입선출(LIFO: Last-In, First-Out)' 방식으로 동작합니다. 즉, 가장 나중에 들어간 요소가 가장 먼저 나오는 방식입니다.

2. 작동 원리 (단계별 설명):

DFS의 작동 원리는 다음과 같은 단계로 이루어집니다.

  1. 시작 노드 설정 및 초기화:
    • 탐색을 시작할 노드를 선택합니다.
    • 방문할 노드를 저장할 stack (스택)을 생성하고, 시작 노드를 스택에 추가합니다. (재귀 구현 시에는 함수 호출 스택이 이 역할을 합니다.)
    • 이미 방문한 노드를 기록할 visited (집합 또는 배열)를 생성하고, 시작 노드를 visited에 추가합니다. (중복 방문 방지)
  2. 스택이 빌 때까지 반복 (또는 재귀 종료 조건까지):
    • stack이 비어있지 않은 동안 다음 단계를 반복합니다. (재귀 함수는 더 이상 호출할 노드가 없으면 반환됩니다.)
  3. 노드 방문:
    • stack의 맨 위에 있는 노드(현재 탐색할 노드)를 꺼냅니다 (pop()).
    • 이 노드를 "방문"합니다. (예: 노드 값 출력, 특정 처리 수행 등)
  4. 인접 노드 탐색 및 스택에 추가:
    • 현재 방문한 노드의 모든 인접(이웃) 노드를 확인합니다.
    • 이웃 노드 중에서 아직 visited에 포함되지 않은 노드를 찾습니다.
    • 찾은 각 이웃 노드를 visited에 추가하고, stack의 맨 위에 추가합니다 (append()). (재귀 구현 시에는 해당 이웃 노드로 dfs 함수를 호출합니다.)
  5. 탐색 종료:
    • stack이 비게 되거나 (반복문), 모든 재귀 호출이 반환되면 (재귀), 모든 연결된 노드를 탐색했음을 의미하며 DFS가 종료됩니다.

3. 파이썬 구현 예시:

DFS는 주로 재귀를 통해 간결하게 구현되거나, 명시적인 스택 자료구조를 사용하여 구현됩니다.

a) 재귀 함수를 이용한 DFS:

Python

# 그래프를 인접 리스트로 표현
graph_dfs_recursive = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited_dfs_recursive = set() # 방문한 노드를 저장할 집합

def dfs_recursive(node):
    # 1. 노드 방문 처리
    visited_dfs_recursive.add(node)
    print(f"  -> 방문: {node}") # 방문한 노드 출력 (예시)

    # 2. 인접 노드 탐색 (재귀 호출)
    for neighbor in graph_dfs_recursive[node]:
        if neighbor not in visited_dfs_recursive:
            dfs_recursive(neighbor) # 방문하지 않은 이웃 노드로 재귀 호출

print("DFS 탐색 시작 (재귀, 시작 노드: A):")
dfs_recursive('A')
print("DFS 탐색 종료.")

# 예상 출력 (순서는 그래프 구조와 재귀 호출 순서에 따라 다를 수 있음. 일반적인 예시):
# DFS 탐색 시작 (재귀, 시작 노드: A):
#   -> 방문: A
#   -> 방문: B
#   -> 방문: D
#   -> 방문: E
#   -> 방문: F
#   -> 방문: C
# DFS 탐색 종료.

b) 스택 자료구조를 이용한 DFS (비재귀):

Python

# 그래프를 인접 리스트로 표현
graph_dfs_stack = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

def dfs_stack(graph, start_node):
    visited = set()
    stack = [start_node] # 파이썬 리스트를 스택처럼 사용
    visited.add(start_node)

    print(f"\\nDFS 탐색 시작 (스택, 시작 노드: {start_node}):")

    while stack:
        current_node = stack.pop() # 스택의 맨 위(가장 나중에 추가된) 노드 꺼내기
        print(f"  -> 방문: {current_node}")

        # 인접 노드를 스택에 추가 (DFS는 보통 나중에 들어온 노드를 먼저 탐색하므로,
        # 인접 노드 리스트를 뒤에서부터 탐색하거나, 스택에 추가할 때 역순으로 넣는 것이 일반적입니다.
        # 여기서는 편의상 순서대로 추가하여 LIFO 원리에 따라 역순으로 탐색되게 합니다.)
        # 실제 문제에서는 이웃 노드의 정렬 순서에 따라 탐색 순서가 달라질 수 있습니다.
        for neighbor in sorted(graph[current_node], reverse=True): # 알파벳 역순으로 추가하여 순서 예측 용이
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor) # 스택에 추가

    print("DFS 탐색 종료.")

# 예시 실행
dfs_stack(graph_dfs_stack, 'A')

# 예상 출력 (정렬 순서에 따라 달라짐. 위 코드 기준):
# DFS 탐색 시작 (스택, 시작 노드: A):
#   -> 방문: A
#   -> 방문: C
#   -> 방문: F
#   -> 방문: E
#   -> 방문: B
#   -> 방문: D
# DFS 탐색 종료.

4. DFS의 특징:

  • 백트래킹 기반: 한 경로를 깊게 파고드는 특성상, 깊은 경로를 탐색하다가 막히면 되돌아와 다른 경로를 시도합니다.
  • 재귀적 구현 용이: 재귀 함수의 호출 스택이 스택 자료구조의 역할을 대신하므로, 코드를 간결하게 작성하기 좋습니다.
  • 최단 경로 보장 안 함: BFS와 달리, DFS는 최단 경로를 보장하지 않습니다. 시작 노드에서 특정 노드까지 가는 가장 짧은 경로가 아닌, 단순히 "경로 중 하나"를 찾아낼 뿐입니다.
  • 완전 탐색: 연결된 모든 노드를 빠짐없이 탐색합니다.
  • 시간 복잡도:
    • 인접 리스트로 구현 시: O(V+E) (V: 노드 수, E: 간선 수). 모든 노드와 간선을 한 번씩만 방문하기 때문입니다.
    • 인접 행렬로 구현 시: O(V2). 각 노드에서 인접 노드를 찾기 위해 행렬의 모든 열을 확인해야 하기 때문입니다.
  • 공간 복잡도: O(V) (재귀 깊이에 따라), 최악의 경우 (선형 그래프) O(V)의 공간이 필요할 수 있습니다.

5. DFS의 주요 활용 분야:

DFS는 주로 다음 문제 해결에 사용됩니다.

  • 사이클 감지 (Cycle Detection): 그래프에 사이클이 존재하는지 여부를 확인하는 데 유용합니다. (방향 그래프에서 특히 중요)
  • 연결된 요소 (Connected Components) 찾기: 그래프 내에서 서로 연결된 노드들의 그룹을 찾는 데 사용됩니다. (BFS도 가능)
  • 위상 정렬 (Topological Sorting): 방향 비순환 그래프(DAG)에서 노드들의 선행 관계를 만족하는 순서를 찾는 데 사용됩니다. (예: 프로젝트 작업 순서, 과목 선수 과목)
  • 경로 찾기 (Pathfinding): 특정 두 노드 사이에 경로가 존재하는지 여부를 확인하거나, 모든 가능한 경로를 탐색할 때 사용됩니다.
  • 미로 찾기: 미로의 한 지점에서 다른 지점까지 가는 경로 중 하나를 찾는 데 활용됩니다. (최단 경로는 BFS)
  • 백트래킹 문제: 모든 가능한 조합이나 순열을 탐색해야 하는 문제 (예: N-Queen 문제, 스도쿠 해결)의 기본 탐색 메커니즘으로 사용됩니다.
  • 강한 연결 요소 (Strongly Connected Components, SCC) 찾기: 방향 그래프에서 서로 도달 가능한 노드들의 집합을 찾는 데 사용됩니다 (코사라주, 타잔 알고리즘 등).
728x90