LeetCode 797번
https://leetcode.com/problems/all-paths-from-source-to-target/

문제

---

생각하기

---

• DFS, 백트래킹 문제이다.

동작

    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