[인접 행렬] 경로탐색 java

문제

방향그래프가주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지수를 출력하는 프로그램을 작성하세요

아래 그래프에서 1번 정점에서 N번 정점으로 가는 가지수는

 

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 줄에 걸쳐 연결정보가 주어진다

 

출력

총가지수 출력한다.

 

입력

5 9

1 2

1 3

1 4 

2 1

2 3

2 5

3 4

4 2

4 5

 

출력 

6

 

내 풀이 

예시 설명

 

 

1번 정점에서 5번 정점으로 가는 모든 경우의 수를 출력

첫번째로 1 2 3 4 5 

-> DFS 재귀 및 백트래킹

-> dfs희 현재 노드에서 갈 수 있는 경우는 1,2,3,4,5번 노드 -> for문 5번

-> 이미 방문했다면 방문하지 않음 -> 방문 배열 생성

-> 종착점인 5번 정점으로 도달했다면 정답 1 증가, 백트래킹을 방문배열 초기화와 함께 진행

-> 연결된 노드에 이어서 진행

 

import java.util.Scanner;


public class Main {
    static int n, m, answer = 0;
    static int[][] graph;
    static int[] ch;//방문배열

    public static void dfs(int v) {
        if(v == n) answer++;//경우의 수 찾음
        else {
            for(int i = 1; i<=n; i++) {
                if(graph[v][i] == 1 && ch[i] != 1) {//갈 정점이 있으면
                    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];//n번 정점까지 나와야함
        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;//시작 정점 1 -> 방문처리
        T.dfs(1);

        System.out.print(answer);


    }

}