DFS 템플릿

1. 그래프 구성

List<List<Integer>> graph = ArrayList<>() {{
    add(List.of(1, 3, 6));
    add(List.of(0, 3));
    add(List.of(3));
    add(List.of(0, 1, 2, 7));
    add(List.of(5));
    add(List.of(4, 6, 7));
    add(List.of(0, 5));
    add(List.of(3, 5));
}};

 

2. Set

import java.util.*;

public class DFS {
    public void dfs(List<List<Integer>> graph, Set<Integer> visited, int curVertex) {
        visited.add(curVertex);
        for (int nextVertex : graph.get(curVertex)) {
            if (!visited.contains(nextVertex)) {
                dfs(graph, visited, nextVertex);
            }
        }
    }

    public void solve(List<List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        dfs(graph, visited, 0);
    }
}

3. boolean[]

import java.util.*;

public class DFS {
    public void dfs(List<List<Integer>> graph, boolean[] visited, int curVertex) {
        visited[curVertex] = true;
        for (int nextVertex : graph.get(curVertex)) {
            if (!visited[nextVertex]) {
                dfs(graph, visited, nextVertex);
            }
        }
    }

    public void solve(List<List<Integer>> graph) {
        final int N = graph.size();
        boolean[] visited = new boolean[N];
        dfs(graph, visited, 0);
    }
}