토픽 24 / 82

DFS (Depth-First Search)

그래프의 한 정점에서 가능한 깊이 끝까지 탐색한 후 백트래킹하는 그래프 순회 알고리즘

목적: 경로 탐색, 사이클 검사, 위상 정렬, 강연결 요소

특징: 깊이 우선, 스택/재귀, 백트래킹, 메모리 효율

구현: 재귀(간단) 또는 스택(명시적)

시간 복잡도: O(V + E) - 인접 리스트, O(V²) - 인접 행렬

공간 복잡도: O(V) - 방문 배열, O(h) - 재귀 스택(h = 깊이)

장점: 메모리 효율(경로만), 경로 저장, 백트래킹 자연스러움

단점: 최단 경로 보장 안함, 무한 루프 위험(사이클)

적용사례: 경로 존재 확인, 사이클 검사, 위상 정렬, 강연결 요소(SCC), 미로 탐색, 백트래킹

비교: DFS(깊이/스택/메모리효율) vs BFS(너비/큐/최단경로)

연관: 그래프, BFS, 백트래킹, 위상 정렬, 재귀