함수 진입 직후 방문 표시
`dfs(node)`가 시작되면 먼저 `visited[node] = true`를 실행하고 이웃을 호출합니다. 순환 간선이 다시 들어와도 종료 조건에서 바로 빠집니다.
DFS 상태 시점
방문 체크 시점이 스택 폭증을 막는다
재귀와 반복 DFS는 같은 상태 전개를 하지만 방문 표시가 늦으면 순환 그래프에서 같은 노드가 여러 번 쌓입니다. 표시 시점을 먼저 정하면 순서와 메모리 사용을 함께 통제할 수 있습니다.
pop 직후 또는 push 전에 기준 고정
pop한 뒤 방문 표시를 한다면 중복 push를 허용하고 꺼낼 때 거릅니다. push 전에 표시하면 스택 크기를 더 작게 유지할 수 있습니다.
start 1
1을 방문 처리하고 2, 3을 다음 상태로 둔다.
move 2
2에서 다시 1을 만나면 이미 방문한 상태인지 확인한다.
late mark
표시가 늦으면 1이 반복해서 스택에 들어가 메모리가 커진다.
skip visited
방문 배열을 테스트 케이스마다 새로 만들고 중복 상태를 버린다.
방문 표시 위치
재귀는 함수 진입 직후, 반복은 pop 직후 또는 push 전 중 하나로 통일한다.
이웃 삽입 순서
반복 DFS는 push 순서가 방문 순서를 바꾸므로 기대 출력과 맞춰 둔다.
테스트 초기화
여러 케이스를 풀 때 visited, stack, order를 케이스마다 분리한다.