[JAVA] DFS - 인접 행렬을 사용한 경로 탐색

문제

- 방향 그래프에서 1번에서 N번 정점으로 가는 모든 경로의 가지 수 출력하기

 

- 이동할 수 있는 정점을 체크할 graph, 방문 했었던 위치를 체크하기 위한 배열 ch를 선언한다.

- 정점에서 이동할 수 있는 정점을 graph에 1을 저장해서 체크해준다.

- DFS를 1번부터 실행

- v(현재 정점)과 n(목적지 정점)이 같으면 경로의 수 + 1

- 아닐 경우, 1번~n번 정점으로 갈 수 있는지 체크(graph[x][y]=1 간선으로 이어져 있고 && ch[i] ==0 방문하지 않았던 곳)

- 방문할 수 있는 정점일 경우 방문 체크를 해주고 다음 정점으로 넘어가기 전에 스택 프레임에 D(v)를 넣고 DFS(다음 정점) 실행

- 앞의 과정을 반복해서 n번 정점에 도착하게 되면 다시 돌아와서 ch[i] = 0 방문 체크를 해제 해준다. 

public class Solution {
    static int n, m, answer = 0;
    static int[][] graph; // 정점 체크
    static int[] ch; // 방문 체크
    public void DFS(int v){
        if(v==n){
            answer++;
        } else {
            for(int i=1; i<=n; i++){
                if(graph[v][i]==1 && ch[i]==0){ // v번 행에서 1~n까지 찾을 수 있는 정점 찾기
                    ch[i] = 1; // 방문 체크
                    DFS(i);
                    ch[i] = 0; // DFS 실행 후에 스택 프레임을 통해 다시 되돌아 올때 방문 풀어주기
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution T = new Solution();
        Scanner sc = new Scanner(System.in);
        n = 5; // 정점의 수
        m = 9; // 간선의 수
        graph = new int[n+1][n+1];
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = 1;
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}