알고리즘
DFS
다른 이름: Depth-First Search , 깊이 우선 탐색
정의
Depth-First Search. 깊이 우선 탐색. 그래프/트리를 깊이 우선으로 방문. 스택(재귀 또는 명시적 스택) 사용. 백트래킹, 사이클 검사, 위상 정렬, 경로 탐색에 활용. 최단 경로 보장 안 함(BFS 사용). O(V+E) 시간복잡도
상세 설명
기술 스펙
- 시간복잡도: O(V+E) - 모든 정점(V)과 간선(E) 방문
- 공간복잡도: O(V) - 재귀 스택 또는 명시적 스택
- 구현: 재귀 (함수 호출 스택) 또는 명시적 스택
- 방문 순서: 현재 노드 → 자식 노드 → 형제 노드
- 백트래킹: 막다른 길 도달 시 이전 노드로 복귀
실무 활용
- 경로 탐색: 미로 탈출, 모든 경로 찾기
- 사이클 검사: 그래프에 순환이 있는지 확인
- 위상 정렬: DAG (Directed Acyclic Graph)
- 백트래킹: N-Queen, 순열, 조합
- 연결 요소: 그래프 연결 여부 확인
장점
- 메모리 효율: 스택만 사용 (BFS는 큐 전체)
- 구현 간단: 재귀로 10줄 내외
- 백트래킹 자연스러움: 재귀 종료 시 자동 복귀
- 모든 경로 탐색: 완전 탐색 가능
단점 및 제약
- 최단 경로 불가: BFS 사용 필요
- 스택 오버플로우: 깊이 매우 깊으면 위험
- 방문 순서 비결정적: 인접 리스트 순서에 의존
- 무한 루프: 사이클 있으면 방문 체크 필수
호환성
C++ STL, Python, Java. 모든 그래프 자료구조
표준 정보
표준화 기구: 알고리즘 교과서 표준. ACM ICPC, 코딩 테스트 필수
출시 연도: 1960년