주어진 DAG
의 시작점에서 끝점으로 갈 수 있는 경로들을 반환하는 문제입니다.
( DAG
- 위키피디아 바로가기 )
시작점부터 carrier
에 경로를 담으며 끝점에 도달하면 answer
에 추가하고 return하는 방식으로 구현했습니다.
return 후에는 carrier
에서 현재값을 꺼내고 남은 경로에서 이어나가는 backtracking을 이용했습니다.
저는 backtracking을 잘 못해서 백준 사이트의 n과 m 시리즈를 통해 익숙해지려 노력했습니다.
( n과 m
- 백준 바로가기 ) 차근차근 풀어볼 수 있어서 좋았습니다.
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));
}
}
}