230206 DFS, Depth First Search

트리 혹은 그래프에서 노드를 깊이 우선 탐색하는 알고리즘
노드를 방문한 후, 그 노드에 연결된 모든 노드를 방문하기 전에 방문하지 않은 인접한 노드를 깊이 탐색

기본 형태

리스트나 스택을 이용해 그래프나 트리를 표현
visited 배열을 통해 방문한 노드를 기록

List를 사용한 DFS

class DFS {
    private boolean[] visited;

    public void dfs(int node, List<List<Integer>> graph) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int i = 0; i < graph.get(node).size(); i++) {
            int neighbor = graph.get(node).get(i);
            if (!visited[neighbor]) {
                dfs(neighbor, graph);
            }
        }
    }
}

Stack을 사용한 DFS

class DFS {
    private boolean[] visited;

    public void dfsUsingStack(int node, List<List<Integer>> graph) {
        Stack<Integer> stack = new Stack<>();
        stack.push(node);

        while (!stack.isEmpty()) {
            int currentNode = stack.pop();
            if (!visited[currentNode]) {
                visited[currentNode] = true;
                System.out.print(currentNode + " ");
                for (int i = graph.get(currentNode).size() - 1; i >= 0; i--) {
                    int neighbor = graph.get(currentNode).get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}