경로탐색 DFS - 인접행렬, 인접리스트로 풀기

문제 

방향 그래프가 주어지면 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가지입니다.

 

입력예제

5 9

1 2

1 3

1 4

2 1

2 3

2 5

3 4

4 2

4 5

 

출력예제

6

 

 

먼저 모든 경로의 가지수를 구해야하므로 DFS로 풀어야한다.

첫번째로 인접행렬로 풀었을때는

DFS + 인접행렬

인접행렬이란 N X N의 행렬을 말한다.

public class RouteSearch {
    //7-12. 그래프 경로 탐색(인접 행렬) DFS
    //방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하시오.
    //그래프에서 한번 방문한 노드는 다시 방문하지 않음.

    //하지만 이 방법은 n의 숫자가 커질수록 이 방법은 불필요

    //전역변수
    static int n, m, answer = 0;
    static int[][] graph;
    static int[] ch;

    public static void main(String[] args) {
        RouteSearch T = new RouteSearch();
        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();
            graph[a][b] = 1;
        }
        ch[1] = 1; // 1부터 시작하므로 1에 체크 -> 여기 중요!!!! 먼저 체크하고 시작 해야함.
        T.DFS(1);
        System.out.println(answer);
    }

    public void DFS(int v) {
        //만약에 n이 5라면 즉 1번노드에서 5번 노드까지 왔기 때문에 answer++;
        if (v == n) {
            answer++;
        } else {
            //1번 노드부터 n번 노드까지
            for (int i = 1; i <= n; i++) {
                //1번 정점에서 갈 수 있는 i번 정점을 갈 수 있어야하고, 방문을 안 했어야함,
                // 1번 정점이라면 ,(1 1),(1 2),(1 3),(1 4),(1 5) 이렇게 방문
                if (graph[v][i] == 1 && ch[i] == 0) {
                    ch[i] = 1;
                    DFS(i);

                    //다시 백 했을 때 다시 체크 풀어주기
                    ch[i] = 0;
                }
            }
        }
    }
}

하지만 이렇게 인접행렬의 방법을 쓰면 n이 커질수록 모든 n을 돌면서 행렬을 체크해야하므로 비효율적이다. 따라서 인접 리스트의 방법을 쓸수 있다.

DFS + 인접리스트

인접리스트란 연결된 노드들의 리스트를 말한다.

 

public class RouteSearch {
    //7-13. 경로탐색(인접리스트, ArrayList)
    //방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하시오.

    //선언만 하고 생성된 상태 X
    static int n, m, answer = 0;

    //선언 및 초기화
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] ch;

    public int DFS(int v) {
        if (v == n) {
            answer++;
        } else {
            //1번 arrayList부터 시작
            for (int nextV : graph.get(v)) {
                if (ch[nextV] == 0) {
                    ch[nextV] = 1;
                    DFS(nextV);
                    ch[nextV] = 0;
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {
        RouteSearch T = new RouteSearch();
        Scanner in = new Scanner(System.in);

        // 정점의 갯수
        n=in.nextInt();
        // 간선의 갯수
        m=in.nextInt();
        // 인접리스트 초기화 - 값을 최초로 할당
        //graph = new ArrayList<ArrayList<Integer>>();


        //n개의 arrayList 객체를 생성해서 graph에 넣어주기
        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 = in.nextInt();
            int b = in.nextInt();
            graph.get(a).add(b);
            //a번 ArrayList에 접근해서 B 값 넣기
            //만약 (1,3) 이라면 1번 arrayList에 3번 원소를 저장.
        }

        //처음에 항상 체크해주기!
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}