DFS: 명시적 스택으로 재귀 깊이와 Java 메모리를 통제하기

DFS는 현재 경로에서 갈 수 있는 한 깊이 진행한 뒤 막히면 가장 최근 분기로 돌아온다. 재귀는 이 규칙을 표현하는 한 구현일 뿐이다. 외부 입력 graph의 깊이가 제한되지 않으면 Java method recursion은 StackOverflowError 위험이 있으므로 명시적 stack이 운영상 더 안전할 수 있다.

1. 문제 계약과 순회 순서

입력은 adjacency int[][] graph와 source다. source에서 도달 가능한 정점을 pre-order로 한 번씩 반환한다. 예제는 adjacency에 적힌 작은 index 순서를 먼저 방문하도록, 명시적 stack에는 neighbor를 역순 push한다. 분리된 정점은 결과에 포함하지 않는다.

DFS의 순회 순서는 graph 구조만으로 유일하지 않다. adjacency iteration과 push 순서에 의존한다. 순서가 business contract라면 정렬 비용과 결정성을 명시해야 한다.

2. 상태 추적과 방문 시점

graph 0:[1,2], 1:[0,3], 2:[0,4]를 본다.

pop	방문 여부	역순 push	stack top→	order
0	새 방문	2, 1	`1,2`	`[0]`
1	새 방문	3	`3,2`	`[0,1]`
3	새 방문	없음	`2`	`[0,1,3]`
2	새 방문	4	`4`	`[0,1,3,2]`
4	새 방문	없음	empty	`[0,1,3,2,4]`

예제는 push 시점에 discovered 표시를 한다. 같은 정점이 여러 predecessor에서 보여도 stack에는 한 번만 들어가므로 고정 int[V] capacity의 근거가 된다. pop 시점까지 미루는 variant는 중복 push를 허용하므로 동적 stack이나 더 큰 상한이 필요하다.

3. 불변식과 종료

불변식: stack에는 발견했지만 아직 처리하지 않은 정점이 각각 한 번씩 LIFO 순서로 있고, discovered[v]는 v가 이미 stack에 들어갔거나 처리됐음을 뜻한다. neighbor를 push하기 전에 표시하므로 중복 edge와 cycle에서도 같은 정점이 다시 들어가지 않는다.

유한 graph에서 정점은 한 번만 처리되고 adjacency entry도 유한하므로 종료한다. visited가 없으면 0-1-0 cycle에서 push가 끝나지 않는다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class DfsDemo {
    static List<Integer> iterativePreorder(int[][] graph, int source) {
        validate(graph, source);
        boolean[] discovered = new boolean[graph.length];
        int[] stack = new int[Math.max(1, graph.length)];
        int size = 0;
        stack[size++] = source;
        discovered[source] = true;
        List<Integer> order = new ArrayList<>();
        while (size > 0) {
            int current = stack[--size];
            order.add(current);
            for (int i = graph[current].length - 1; i >= 0; i--) {
                int next = graph[current][i];
                if (next < 0 || next >= graph.length) throw new IllegalArgumentException("invalid edge");
                if (!discovered[next]) {
                    discovered[next] = true;
                    stack[size++] = next;
                }
            }
        }
        return order;
    }

    static void validate(int[][] graph, int source) {
        if (graph == null) throw new IllegalArgumentException("graph must not be null");
        if (source < 0 || source >= graph.length) throw new IllegalArgumentException("invalid source");
        for (int[] edges : graph) if (edges == null) throw new IllegalArgumentException("adjacency must not be null");
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        int[][] graph = {{1, 2}, {0, 3}, {0, 4}, {1}, {2}, {}};
        List<Integer> order = iterativePreorder(graph, 0);
        check(order.equals(Arrays.asList(0, 1, 3, 2, 4)), "preorder");
        check(!order.contains(5), "disconnected");
        check(iterativePreorder(new int[][] {{}}, 0).equals(List.of(0)), "single");
        System.out.println("preorder=" + order + ", disconnected 5=false");
    }
}

javac --release 21 DfsDemo.java
java DfsDemo

직접 실행한 출력은 다음과 같다.

preorder=[0, 1, 3, 2, 4], disconnected 5=false

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

4. 예제 stack capacity의 근거와 경계

int[V] stack이 충분한 이유는 모든 정점을 push 직전에 discovered로 바꾸기 때문이다. 한 정점은 최대 한 번만 stack에 들어가므로 동시에 든 entry 수도 V를 넘지 않는다. 이 순서를 pop 시점 표시로 바꾸면 같은 정점이 여러 경로에서 중복 push되어 이 capacity 증명이 사라진다.

정점 수를 미리 모르는 streaming graph라면 동적 ArrayDeque<Integer>가 맞다. 이때도 discovered 시점은 중복 frontier와 메모리 peak를 좌우한다.

5. 시간·공간 복잡도

각 정점을 최대 한 번 처리하고 처리된 정점의 adjacency를 한 번 훑으므로 $O(V+E)$ 다. visited와 stack은 $O(V)$ 를 목표로 하며 결과 order도 도달 정점 수 $R$ 만큼 $O(R)$ 이다. 입력 graph 저장 $O(V+E)$ 는 별도다.

재귀 DFS도 알고리즘 state는 $O(V)$ 이지만 path depth $D$ 만큼 method frame이 중첩된다. 명시적 stack은 heap에 frontier를 보관한다. Big-O가 같아도 실패 형태가 StackOverflowError와 heap pressure로 다르다.

6. JVM Stack/Heap 실행 경로

JVMS는 thread마다 private JVM Stack과 invocation마다 frame이 생긴다고 정의한다. 재귀 깊이만큼 frame이 살아 있고 허용 크기를 넘으면 StackOverflowError다. 구체 frame byte와 물리 배치는 구현 세부다.

명시적 int[] stack, boolean[] visited, ArrayList<Integer>와 boxed result는 heap에 있다. 결과 list의 Integer boxing을 피하려면 int[]와 count를 반환할 수 있지만 API ergonomics와 실제 allocation을 측정한 뒤 선택한다.

7. BFS와 반대라기보다 frontier 정책이 다르다

기준	DFS	BFS
frontier	LIFO	FIFO
무가중 최소 hop	보장 안 함	보장
memory peak	깊은 path/분기 후보	넓은 layer
자연스러운 작업	cycle, component, backtracking	layer, shortest hops

DFS로 먼저 찾은 path는 shortest가 아닐 수 있다. 반대로 모든 layer를 저장할 필요 없는 깊은 탐색에서는 BFS frontier가 더 클 수 있다.

8. 실제 도메인 적용

dependency cycle 검사, filesystem tree walk, compiler AST traversal, backtracking search에 쓴다. symlink cycle이나 graph cycle을 visited 없이 순회하면 무한 반복한다. 관측 지표는 visited count, max explicit stack size/recursion depth, rejected depth, traversal timeout이다. 파일 순회는 permission error와 TOCTOU, symlink 정책이 알고리즘 밖의 필수 계약이다.

9. 이건 피한다

외부 입력 graph를 무제한 재귀로 순회한다. 깊은 chain이 StackOverflowError를 낸다. depth limit이나 명시적 stack을 쓴다.
cycle graph에서 visited를 생략한다. 종료하지 않거나 같은 정점을 반복 처리한다. 발견/방문 상태를 둔다.
DFS 첫 경로를 최단 경로라 부른다. traversal order에 따른 한 경로일 뿐이다. 무가중 최소 hop은 BFS를 쓴다.
순회 순서가 고정이라고 가정한다. adjacency collection iteration에 따라 달라진다. 결정성이 필요하면 정렬/ordered input 계약을 둔다.
pop 때까지 discovered 표시를 미룬 채 고정 V stack을 쓴다. 중복 push로 capacity를 넘을 수 있다. push 직전에 표시하거나 동적 deque를 쓴다.

Reference

Robert Sedgewick, Kevin Wayne, Algorithms, 4th Edition — Undirected Graphs
Robert Sedgewick, Kevin Wayne, DepthFirstPaths.java
Oracle, ArrayDeque — Java SE 21 API
Oracle, The Java Virtual Machine Specification, Java SE 21 — JVM Stacks and Frames
Oracle, StackOverflowError — Java SE 21 API