그래프, 경로탐색, 인접행렬, DFS

✅ 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경우의 가지 수를 구하세요

✔️ 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다.

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

✔️ input

5 9 //정점 노드 수, 간선 수
1 2 //여기서부터 연결 정보
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

✔️ 그래프 그림

🔵 ThingsILearned

• 평소같으면 psvm안에서 설정하는 배열, int n, m=0, int answer=0같은 것들이 모두 static으로 Main에 들어왔다.
• 그 이유는 변수와 배열들이 psvm 뿐만 아니라 Main Class에서도 쓰이기 떄문이다.

⭐️ 왜 int answer=0도 static으로 해야 할까?

정답은 DFS 재귀함수에 있다.
만약 answer을 DFS함수 안에 local variable로 declare 했다면,
DFS가 실행될 떄마다 answer=0으로 초기화 될 것이다.

💡 Static?

• static menas that the static value will maintain its value throughout the entire execution of the program
• and it is shared across all recursive class

✔️ psvm

• 입력을 받고 2차원 배열인 인접행렬을 만드는 기능을 한다.
• 인접행렬 graph는 index가 1부터 시작하기 떄문에 graph의 크기는 n+1이다.

• 입력 받은 값을 보고 두 노드가 연결되어 있으면 길이 있다고 알려준다. graph[a][b]=1

• ch배열은 이 노드에 갔었는지 안 갔었는지 확인하는 배열이다.
  왜냐하면 그래프에서 경로란, 한번 방문한 노드는 재방문할 수 없기 때문이다.
  (재방문 가능하면 경우의 수 무한해 질 것이다)
  
• 노드에 갔으면 1이라고 체크한다.
• 노드 1에서 시작하기에 1번 노드는 갔다고 체크하기 ch[1]=1
• 그리고 되돌아갈 때는 안 갔던 길이라고 체크해주기 필수❗️

✔️ DFS 함수

• parameter로 int v를 받는다.
• int v는 현재 몇 번째 행에 있는지 알려준다.

• 즉, 내가 지금 몇 번째 노드에서 출발하는지 알려준다.

• 만약 내가 5번 노드에 도착했다면 answer++

• 아니라면, 내가 갈 수 있는 길을 알아야 하니까
• for문을 돌면서 갈수 있는 길인지(graph[v][i]가 0이 아닌지)확인하고
• 내가 갔던 길이 아닌지 확인(ch[i] ==0)
• 갈 수 있는 길이면 길을 가고, 갔던 길이라고 체크
• 길 가기 DFS(i)
• 길 갔다 온 다음에는 안 갔던 길이라고 다시 설정 ch[i]=0 ❗️
• 체크를 풀어주지 않으면 되돌아 갔을 때도 갔었던 길이라고 생각해 그 노드쪽으로 가지 않는다. ❗️
• 따라서 되돌아 갈 때는 안 갔던 길이라고 체크해주기 필수 ❗️

🟢 CODE

class Main {
    static int[][] graph;
    static int[] ch;
    static int answer=0;
    static int n, m=0;

    public void DFS(int v) {
        if(v==n) answer++;
        else{
            for(int i=1; i<=n; i++){
                    if(graph[v][i] !=0 && ch[i] ==0) { //길이 있고 아직 안 간 길이면
                        ch[i]=1; //갔다고 체크하고
                        DFS(i);
                        ch[i]=0; //되돌아갈 때는 체크 풀어주기
                }
            }
        }
    }
    public static void main(String[] args) {
        Main T= new Main();
        Scanner sc= new Scanner(System.in);
        n= sc.nextInt();
        m= sc.nextInt();
        graph = new int[n+1][n+1]; //인덱스는 1부터 시작
        ch= new int[n+1];
        for(int i=0; i<m; i++){ //간선 수 만큼
            int a= sc.nextInt();
            int b= sc.nextInt();
            graph[a][b]=1;
        }
        ch[1]=1;
        T.DFS(1); //1번 노드에서 시작
        System.out.print(answer);
    }
}