DFS + 인접리스트 경로수 탐색

DFS에서 ArrayList로 Graqph를 만드는 경우입니다.

// 13.경로탐색, 인접리스트
public class RouteNaviDFS2 {
    static int n, m, answer = 0;      // n : 정점, m : 간선
    static List<List<Integer>> graph = null;  // 인접리스트
    static int[] ch;                // 방문체크 배열

    public void DFS(int v) {
        if (v == n) answer++;          // (v==n) 최종 정점에 도착할 시 경우수 count +1!
        else {
            for(int nv : graph.get(v)){
                if(ch[nv]==0){
                    ch[nv]=1;
                    DFS(nv);
                    ch[nv]=0;
                }
            }
        }
    }

    public static void main(String[] args) {
        RouteNaviDFS2 T = new RouteNaviDFS2();

        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();

        graph = new ArrayList<>();        // n+1(실제 n) 정점 -> n+1(실제 n) 정점 간다
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>());
        }

        ch = new int[n + 1];                 // 방문 체크 배열

        for (int i = 0; i < m; i++) {        // 인접 행렬[a][b] 간선 m 개수만큼 a, b 입력
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);             // a 정점 -> b 정점 갔다.
        }
        ch[1] = 1;                      // 1 정점 체크
        T.DFS(1);                    // 1 정점에서 시작
        System.out.println(answer);
    }
}