리트코드 - 797. All Paths From Source to Target

홍성진·2023년 2월 28일
0

리트코드 - 797. All Paths From Source to Target

주어진 DAG의 시작점에서 끝점으로 갈 수 있는 경로들을 반환하는 문제입니다.
( DAG - 위키피디아 바로가기 )

시작점부터 carrier에 경로를 담으며 끝점에 도달하면 answer에 추가하고 return하는 방식으로 구현했습니다.
return 후에는 carrier에서 현재값을 꺼내고 남은 경로에서 이어나가는 backtracking을 이용했습니다.

저는 backtracking을 잘 못해서 백준 사이트의 n과 m 시리즈를 통해 익숙해지려 노력했습니다.
( n과 m - 백준 바로가기 ) 차근차근 풀어볼 수 있어서 좋았습니다.

 

  • leetcode에서 ArrayList 정도는 import하지 않아도 자동으로 포함시켜 주네요.
class Solution {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> answer = new ArrayList<>();
        List<Integer> carrier = new ArrayList<>();
        backtrack(0, graph, carrier, answer);

        return answer;
    }

    public void backtrack(int cur, int[][] graph,
            List<Integer> carrier, List<List<Integer>> answer) {

        carrier.add(cur);

        if (cur == graph.length -1) {
            List<Integer> temp = new ArrayList<>();
            for (int c : carrier) {
                temp.add(c);
            }
            answer.add(temp);

            return;
        }

        for (int n : graph[cur]) {
            backtrack(n, graph, carrier, answer);
            carrier.remove(Integer.valueOf(n));
        }
    }
}

0개의 댓글