알고리즘 7장
그래프 탐색: 반복 DFS 템플릿
반복 DFS는 재귀 호출 스택을 명시적 스택으로 바꾼 구현이며, push 순서가 방문 순서를 결정합니다.
상태 변화
스택 상태
1
2
3
4
5
stack top
4
2
3
order
1
2
4
push 순서가 바뀌면 방문 순서도 달라집니다.
불변식
점검
스택 stack
마지막에 넣은 정점부터 꺼내 한 경로를 깊게 따라갑니다.
역순 push
인접 리스트 순서를 유지하려면 뒤에서부터 넣는 구현이 흔합니다.
방문 시점
pop 후 방문 처리하면 중복 push가 생길 수 있어 조건을 확인해야 합니다.
재귀 대체
깊은 입력에서 런타임 스택 제한을 피하는 선택지입니다.