99클럽 코테 스터디 8일차 TIL [LeetCode] All Paths From Source to Target (Java)

문제

[LeetCode] All Paths From Source to Target

풀이

• 깊이 우선 탐색(DFS)을 수행하며, 백트래킹을 통해 모든 가능한 경로를 탐색한다.

정답 코드

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), graph, 0, graph.length - 1);
        return result;
    }

    public void dfs(List<List<Integer>> result, List<Integer> path, int[][] graph, int start, int end) {
        path.add(start);
        if (start == end) {
            result.add(new ArrayList<>(path));
        } else {
            for (int node : graph[start]) {
                dfs(result, path, graph, node, end);
            }
        }
        path.remove(path.size() - 1);
    }

}