leetcode 리트코드 797 All Paths From Source To Target

문제 : (1) All Paths From Source to Target - LeetCode

All Paths From Source to Target - LeetCode

 

풀이  : DFS

 

구현 JAVA

 

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        
        boolean[] isVisited = new boolean[graph.length];
        Queue<Integer> queue = new LinkedList<>();
        List<List<Integer>> answer = new LinkedList<>();
        List<Integer> route = new LinkedList<>();
        //시작위치 저장
        isVisited[0] =true;
        route.add(0);
        //DFS 탐색 시작
        dfs(graph, isVisited, 0, route,  answer);

        return answer;
    }

    private void dfs(int[][] graph, boolean[] isVisited, int now, List<Integer> route, List<List<Integer>> answer) {
        if(now ==graph.length-1){
            List<Integer> add = new LinkedList<>(route);
            answer.add(add);
            return;
        }
        for(int v : graph[now]){
            if(!isVisited[v]){
                isVisited[v]=true;
                route.add(v);
                dfs(graph, isVisited, v, route, answer);
                isVisited[v] = false;
                route.remove(route.size()-1);
            }
        }
    }
}