LeetCode 797번
https://leetcode.com/problems/all-paths-from-source-to-target/
private void DFS(LinkedList<Integer> deque, int current, int index, int[][] graph) {
if(N - 1 == current) {
List<Integer> list = new ArrayList<>(deque);
adjList.add(list);
return;
}
for(int i=0; i<graph[current].length; i++) {
deque.offerLast(graph[current][i]);
DFS(deque, graph[current][i], index, graph);
deque.pollLast();
}
} // End of DFS()
deque
를 이용해서 백트래킹을 구현했는데, 일반적인 조합에서는 comb[]
배열로 많이 사용하는데, 여기서는 방향 그래프로 몇 개의 노드를 방문해야 되는지 모르기 때문에 가변성의 가지는 크기인 List가 필요했는데, 넣고 빼기는 Dequeue 만큼 좋은게 없는 것 같아서 사용했다.
그 외에는 특별한게 없다.
import java.util.*;
class Solution {
private static int N;
private static List<List<Integer>> adjList;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
input(graph);
LinkedList<Integer> deque = new LinkedList<>();
deque.offer(0);
DFS(deque, 0, 0, graph);
return adjList;
} // End of solution()
private void DFS(LinkedList<Integer> deque, int current, int index, int[][] graph) {
if(N - 1 == current) {
List<Integer> list = new ArrayList<>(deque);
adjList.add(list);
return;
}
for(int i=0; i<graph[current].length; i++) {
deque.offerLast(graph[current][i]);
DFS(deque, graph[current][i], index, graph);
deque.pollLast();
}
} // End of DFS()
private void input(int[][] graph) {
N = graph.length;
adjList = new ArrayList<>();
} // End of input();
} // End of Solution class