Q. 개념

---

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프
로그램을 작성하세요. 아래 그래프에서 1번 정점에서 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
총 6 가지입니다.

▣ 입력설명
첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보가 주어진다.

▣ 출력설명
총 가지수를 출력한다.

▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

▣ 출력예제 1
6

전략

• 이번 강에서는 그래프를 인접행렬로 표현
• 그래프 경로 구하기 : 한번 방문한 노드는 재방문하지 않음
• 구조

  [상태트리구조]
  
  [스택구조]

정답

import java.util.*;
class Main {
    static int n, m, answer=0;
    static int[][] graph;
    static int[] ch;
    public void DFS(int v){
        if(v==n) answer++;
        else{
            // 1번 노드부터 n번 노드까지
            for(int i=1; i<=n; i++){
                // graph[v][i]==1 : 현재 노드(v)에서 갈 수 있는 노드(i)들
                // ch[i]==0 : 가야할 i 노드는 방문 된 적 없어야함
                if(graph[v][i]==1 && ch[i]==0){
                    ch[i]=1;
                    DFS(i);
                    // 윗줄 DFS(i);가 pop 된 후 복귀(백트래킹) 하는 시점에서 다시 체크 풀어줌
                    // -> DFS(i); 전에 했던 일을 후에 반대로 하면 취소 됨
                    ch[i]=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 int[n+1][n+1];
        ch=new int[n+1];
        for(int i=0; i<m; i++){
            int a=kb.nextInt();
            int b=kb.nextInt();
            // 단방향 그래프 : a->b
            graph[a][b]=1;
        }
        ch[1]=1;
        T.DFS(1);
        System.out.println(answer);
    }
}