[Java] DFS

스택 DFS를 사용하는 것이 더 안전 (재귀는 스택 오버플로우 위험)

import java.util.Stack;

public class Main {

    private static boolean[] visited;
    
    public static void main(String[] args) {
    	// 예제 그래프 초기화 (0번부터 8번까지의 노드)
    	int n = 9;
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 추가 (양방향)
        addEdge(0, 1);
        addEdge(0, 2);
        addEdge(1, 3);
        addEdge(1, 4);
        addEdge(2, 5);
        addEdge(2, 6);
        addEdge(3, 7);
        addEdge(4, 8);
        
        visited = new boolean[n];
        
        dfsRecursive(0);
        
        dfsIterative(0);
    }
           
    // 그래프에 간선 추가 (양방향)
    private static void addEdge(int u, int v) {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    // 재귀
    public static void dfsRecursive(int node) {
    	StringBuilder sb = new StringBuilder();
    
        visited[node] = true;
        sb.append(node + " ");
        
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor] {
                dfsRecursive(neighbor);
            }
        }
        System.out.println(sb.toString());
    }
    
    // 스택
    public static void dfsIterative(int start) {
        StringBuilder sb = new StringBuilder();
        Static<Integer> Stack = new Stack();
        boolean[] visited = new boolean[graph.size()];
        
        // 시작 노드 처리
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int current = stack.pop();
            
            if (!visited[current]) {
                visited[current] = true;
                sb.append(current + " ");
                
                // 인접 노드들을 스택에 추가 (순서 유지를 위해 역순으로)
                List<Integer> neighbors = graph.get(current);
                for (int i = neighbor.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        System.out.println(sb.toString());
    }
}