[자료구조] DFS 이란?

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

 

깊이 우선 탐색(DFS, Depth-First Search)은 그래프와 트리와 같은 자료구조에서 사용되는 탐색 알고리즘 중 하나입니다. 이 알고리즘은 어떤 시작 노드에서 출발하여 가능한 한 깊이 들어가서 더 이상 진행할 수 없을 때까지 탐색을 진행한 후, 다음 분기로 넘어가는 방식을 취합니다.

DFS의 주요 특징

 

1. 재귀 또는 스택 사용

 

DFS는 주로 재귀 함수 호출 또는 스택을 사용하여 구현됩니다. 각 노드를 방문하면 스택에 현재 노드를 추가하고, 더 이상 진행할 수 없을 때 스택에서 이전 노드로 돌아갑니다.

 

 

2. 깊이 우선

 

DFS는 한 분기를 깊이 탐색하며, 더 이상 진행할 수 없을 때까지 계속 진행합니다. 따라서 가장 깊이 있는 노드를 먼저 탐색하고 나중에 돌아옵니다.

 

3. 모든 노드 탐색

 

DFS를 통해 모든 노드를 탐색할 수 있으며, 그래프나 트리가 연결되어 있을 때 주로 사용됩니다.

DFS는 주로 다음과 같은 문제를 해결하는 데 사용됩니다

- 그래프 순회
- 노드의 연결 여부 확인
- 경로 찾기
- 트리 구조 파악

그러나 DFS는 무한 루프에 빠질 수 있으며, 최단 경로 문제에는 적합하지 않을 수 있습니다. 따라서 문제의 특성에 따라 DFS를 사용할 때 주의해야 합니다.

 

 

 

예시 소스코드

 

파이썬으로 DFS를 구현한 예시 코드를 제공해 드리겠습니다. 이 예시 코드에서는 그래프를 인접 리스트로 표현하고, DFS 함수를 통해 깊이 우선 탐색을 수행합니다.

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

# 방문한 노드를 추적하기 위한 리스트
visited = []

# DFS 함수 정의
def dfs(node):
    global visited
    if node not in visited:
        print(node, end=' ')  # 현재 노드 출력
        visited.append(node)
        for neighbor in graph[node]:
            dfs(neighbor)

# 시작 노드를 지정하여 DFS 수행
print("DFS 탐색 결과:")
dfs('A')

 

 

다른 방식 DFS 구현

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]
visited = [False] * 9

dfs(graph, 1, visited)