DFS

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

정의

• DFS는 그래프의 모든 정점을 탐색하는 알고리즘 중 하나로, 가장 깊은 부분을 우선적으로 탐색하는 방식입니다.

사용 예

• 문제: 그래프의 모든 정점 방문, 경로 탐색 등

과정 설명

1. 시작 정점 선택: 탐색을 시작할 정점을 선택합니다.
2. 인접 정점 탐색: 현재 정점에서 갈 수 있는 인접한 정점을 찾습니다.
3. 깊이 우선 탐색: 인접한 정점 중 하나를 선택하여 더 깊게 탐색합니다.
4. 방문 체크: 방문한 정점은 체크하여 중복 방문을 방지합니다.

Sudo Code

def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)