알고리즘

DFS (깊이 우선 탐색)

그래프나 트리에서 한 방향으로 최대한 깊이 탐색한 뒤 되돌아오는 방식. 재귀 또는 명시적 스택으로 구현한다.

핵심 포인트

• 방문 배열(visited)로 무한 루프를 방지
• 사이클 감지, 위상 정렬, 강한 연결 요소 탐색에 활용
• 재귀 깊이가 깊으면 스택 오버플로 발생 — 반복 DFS 고려
• 대표 문제: 미로 탐색, 연결 요소 개수, 백트래킹