★경로 탐색(인접리스트)

방향 그래프의 1번 정점에서 n번 정점으로 가는 모든 경로의 가지 수를 출력하시오.

첫 줄은 정점 , 간선 수

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 2 3 4 5
1 2 5
1 3 4 2 5
1 3 4 5
1 4 2 5
1 4 5 

 

graph.get(1) - [2,3,4]

graph.get(2) - [1,3,5]

graph.get(3) - [4]

graph.get(4) - [2,5]

 

import java.util.*;

public class Main {
    static int n, m, answer = 0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    
    public void DFS(int v) {//현재의 지점은 v
        if(v==n) answer++;
        //뻗어라
        else {
            //v번 arrayList에 있는 리스트 출력
            for(int nv : graph.get(v)) {
                //방문했냐 안 했냐만 판단
                if(ch[nv] == 0) {
                    ch[nv] = 1;
                    DFS(nv);
                    ch[nv] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt(); //노드의 갯수(정점의 갯수)
        m = kb.nextInt(); //간선의 갯수
        graph = new ArrayList<ArrayList<Integer>>();
        //★★★
        for(int i = 0; i < n; i++) {
            graph.add(new ArrayList<Integer>());
        }
        ch = new int[n+1];
        for(int i = 0; i< m; i++) {
            int a = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b); //a번 ArrayList에 접근하여 b를 넣음
        }
        T.DFS(1);
        System.out.println(answer);
    }

}