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

깊이 우선 탐색은 그래프 또는 트리를 탐색할 때, 한 노드에서 시작하여 각 분기를 가능한 한 깊게 탐색하는 알고리즘입니다.

• 스택(Stack): DFS는 스택을 사용하여 이미 방문한 노드를 추적합니다.

• 재귀(Recursion): 스택을 명시적으로 사용하지 않고, 재귀 호출을 통해 구현될 수 있습니다.

• 경로 탐색: DFS는 시작 노드에서 목표 노드까지의 경로를 찾는데 자주 사용됩니다.

• 시간 복잡도: (O(|V| + |E|)), 여기서 (|V|)는 정점의 수, (|E|)는 간선의 수입니다.

1. 노드 선택: 탐색을 시작할 노드를 선택합니다.

2. 방문 및 탐색: 선택한 노드를 방문하고, 인접한 노드 중 방문하지 않은 노드로 이동합니다.

3. 재귀적 탐색: 각 노드에서 재귀적으로 DFS를 수행하여, 가능한 깊게 탐색합니다.

4. 탐색 완료: 더 이상 방문할 노드가 없을 때 탐색을 종료합니다.

• 깊이 우선: 각 분기를 끝까지 탐색한 후에 다른 분기로 넘어갑니다.

• 백트래킹(Backtracking): 이미 방문한 노드나 경로를 되돌아가면서 다른 경로를 탐색합니다.

• 비순환 그래프(Non-Cyclic Graphs): DFS는 비순환 그래프에서 모든 노드를 방문하는 데 효과적입니다.

• 탐색 순서: 노드의 탐색 순서는 그래프의 구조와 시작 노드에 따라 달라집니다.

• 장점: 간단하고, 모든 노드를 방문하는 것을 보장합니다. 메모리 사용이 상대적으로 적습니다.

• 단점: 최단 경로를 찾는데는 적합하지 않을 수 있습니다. 순환 경로가 있는 그래프에서는 무한 루프에 빠질 위험이 있습니다.