알고리즘 그래프 탐색 - DFS(깊이 우선 탐색)

DFS(깊이 우선 탐색)

DFS(Depth-First Search)는 그래프나 트리 구조를 탐색하는 알고리즘 중 하나이다. 이 알고리즘은 가능한 한 깊이 들어가면서 탐색을 진행하고, 더 이상 탐색할 수 없을 때 백트래킹(backtracking)하여 다른 경로를 탐색한다. DFS는 주로 스택이나 재귀 함수를 사용하여 구현한다. 스택을 사용하면 명시적으로 방문할 노드를 관리할 수 있고, 재귀를 사용하면 함수 호출 스택을 이용하여 자동으로 백트래킹을 처리할 수 있다. 이 알고리즘의 특징은 한 경로를 끝까지 탐색한 후 다른 경로를 탐색한다는 점이다. 이는 미로 찾기나 경로 탐색 문제 등에서 유용하게 사용된다. 

 

DFS 핵심 메커니즘

• DFS는 가능한 한 깊이 들어가면서 탐색을 진행한다. 한 경로를 끝까지 탐색한 후 다른 경로로 이동한다.
• DFS는 일반적으로 스택이나 재귀를 사용하여 구현된다. 이는 LIFO(Last In, First Out) 원칙을 따르므로 가장 최근에 발견한 노드를 먼저 탐색한다. 
• 더 이상 탐색할 노드가 없으면 이전 분기점으로 돌아가는 백트래킹을 수행한다. 

 

작동 원리 

1. 시작 노드를 선택하고 방문 표시를 한다. 
2. 현재 노드와 인접한 노드 중 방문하지 않은 노드를 선택한다. 
3. 선택한 노드로 이동하고 방문 표시를 한다 
4. 2-3 과정을 반복한다. 
5. 더이상 방문할 수 있는 인접 노드가 없으면 이전 노드로 돌아간다. (=백트래킹)
6. 모든 노드를 방문할 때까지 2-5 과정을 반복한다. 

작동 방식

단계별 작동 방식

1. A 노드를 방문한다.
2. A의 인접 노드인 B를 방문한다. 
3. B의 인접 노드인 D를 방문한다. 
4. B로 백트래킹한 후, B의 다른 인접 노드인 E를 방문한다. 
5. A로 백트래킹한 후, A의 다른 인접 노드인 C를 방문한다. 
6. 마지막으로 C의 인접 노드인 F를 방문하여 모든 노드를 탐색 완료한다.

 

 

그래프 표현하기 

① 인접 리스트 표현 

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

② 인접 행렬 표현 

graph = [
    [0, 1, 1, 0, 0, 0],  # A
    [1, 0, 0, 1, 1, 0],  # B
    [1, 0, 0, 0, 0, 1],  # C
    [0, 1, 0, 0, 0, 0],  # D
    [0, 1, 0, 0, 0, 0],  # E
    [0, 0, 1, 0, 0, 0]   # F
]

 

파이썬 코드로 구현하기

① 스택 사용하기

def dfs_stack(graph, start):
    # 방문한 노드를 추적하기 위한 집합(set)
    visited = set()
    # DFS를 위한 스택, 시작 노드로 초기화
    stack = [start]
    
    while stack:  # 스택이 비어있지 않은 동안 반복
        # 스택에서 노드를 꺼냄 (현재 방문할 노드)
        vertex = stack.pop()
        
        # 현재 노드를 아직 방문하지 않았다면
        if vertex not in visited:
            # 노드를 출력 (방문 순서 확인용)
            print(vertex, end=' ')
            # 노드를 방문 처리
            visited.add(vertex)
            
            # 현재 노드의 이웃 노드들을 스택에 추가
            # 방문하지 않은 이웃 노드만 추가하고, 역순으로 추가하여 그래프 순서대로 방문
            stack.extend(reversed([n for n in graph[vertex] if n not in visited]))

# 그래프 정의 (딕셔너리 사용)
graph = {
    'A': ['B', 'C'],  # A는 B, C와 연결됨
    'B': ['A', 'D', 'E'],  # B는 A, D, E와 연결됨
    'C': ['A', 'F'],  # C는 A, F와 연결됨
    'D': ['B'],  # D는 B와 연결됨
    'E': ['B'],  # E는 B와 연결됨
    'F': ['C']   # F는 C와 연결됨
}

print("스택을 사용한 DFS (시작 노드: 'A'):")
dfs_stack(graph, 'A')

# 실행 결과:
# 스택을 사용한 DFS (시작 노드: 'A'):
# A C F B E D

② 재귀 사용하기 

def dfs_recursive(graph, start, visited=None):
    # 방문한 노드를 추적하기 위한 집합(set)
    if visited is None:
        visited = set()
    
    # 현재 노드를 방문 처리
    visited.add(start)
    # 현재 노드 출력 (방문 순서 확인용)
    print(start, end=' ')
    
    # 현재 노드의 모든 이웃 노드에 대해
    for neighbor in graph[start]:
        # 아직 방문하지 않은 이웃 노드라면
        if neighbor not in visited:
            # 해당 이웃 노드에 대해 재귀적으로 DFS 수행
            dfs_recursive(graph, neighbor, visited)

# 그래프 정의 (딕셔너리 사용)
graph = {
    'A': ['B', 'C'],  # A는 B, C와 연결됨
    'B': ['A', 'D', 'E'],  # B는 A, D, E와 연결됨
    'C': ['A', 'F'],  # C는 A, F와 연결됨
    'D': ['B'],  # D는 B와 연결됨
    'E': ['B'],  # E는 B와 연결됨
    'F': ['C']   # F는 C와 연결됨
}

print("재귀를 사용한 DFS (시작 노드: 'A'):")
dfs_recursive(graph, 'A')

# 실행 결과:
# 재귀를 사용한 DFS (시작 노드: 'A'):
# A B D E C F

 

모든 재귀 함수는 스택을 사용하여 반복적(iterative) 방식으로 변환할 수 있다. 이는 컴퓨터가 내부적으로 재귀 호출을 처리하는 방식과 유사하다. 또한 스택을 사용하는 알고리즘은 대부분 재귀적으로 재작성할 수 있다. 실제로 어느 방식을 선택할지는 문제의 특성, 가독성, 성능 요구사항 등을 고려하여 결정해야 한다. 두 방식 모두 장단점이 있으며, 상황에 따라 적절한 방식을 선택하는 것이 중요하다. 

 

참고로 재귀는 간결하고 직관적인 코드를 선호하거나 그래프가 너무 크지 않은 경우에 적합하다. 반면, 스택 기반 구현은 매우 큰 그래프, 탐색 과정의 세밀한 제어가 필요한 경우, 또는 시스템의 스택 크기 제한을 우회해야 할 때 유용하다.