DFS + 인접행렬 경로수 탐색

public class RouteNaviDFS {
    static int n, m, answer=0;      // n : 정점, m : 간선
    static int[][] graph;           // 인접그래프
    static int[] ch;                // 방문체크 배열
    public void DFS(int v){
        if(v==n) answer++;          // (v==n) 최종 정점에 도착할 시 경우수 count +1!
        else{
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){
                    ch[i]=1;        // 방문 체크
                    DFS(i);
                    ch[i]=0;        // 방문 풀어야 백하기 위해
                }
            }
        }
    }

    public static void main(String[] args){
        RouteNaviDFS T = new RouteNaviDFS();
        Scanner kb = new Scanner(System.in);
        n=kb.nextInt();
        m=kb.nextInt();
        graph=new int[n+1][n+1];        // n+1(실제 n) 정점 -> n+1(실제 n) 정점 간다
        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[a][b]=1;              // a 정점 -> b 정점 갔다.
        }
        ch[1]=1;                        // 1 정점 체크
        T.DFS(1);                    // 1 정점에서 시작
        System.out.println(answer);
    }
}