문제

5개의 정점을 가지는 방향 그래프의 모든 경로의 가지 수를 출력하는 프로그램을 작성하는 문제가 있다. 이때 입력되는 예시는

5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 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개가 존재한다. 이를 DFS 알고리즘을 사용하여 풀어내보자.

코드

public class AdjacencyMatrix2ArrayList {
    static int n,m,answer = 0;
    static ArrayList<ArrayList<Integer>> graph;
    static int[] ch;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        ch = new int[n+1];
        for(int i=0; i<m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
        ch[1] = 1;
        dfs(1);
        System.out.println(answer);
    }
    public static void dfs(int v){
        if(v==n){
            answer ++;
            return ;
        }
        for(int nv : graph.get(v)){
            if(ch[nv] == 0){
                ch[nv] = 1;
                dfs(nv);
                ch[nv] = 0;
            }
        }
    }
}

설명

경로 탐색에 인접 행렬은 정점의 수가 작을때는 괜찮지만 정점의 갯수가 10000개라면? 그때는 메모리의 크기가 10000씩 두개의 배열이 필요해지는데 메모리 낭비가 심하게 되며 탐색할때도 매 정점을 탐색할때마다 만번씩 탐색해야한다. 그래서 인접리스트 개념을 공부해야한다.

인접리스트는 정점의 갯수만큼 arrayList를 생성한다. 그리고나서 간선의 정보를 해당 정점에 간선의 정보를 추가한다.

위 그림의 그래프를 기준으로 리스트를 생성하면

1 [2,3,4]
2 [1,3]
3 [4]
4 [2,5]
5

의 리스트와 리스트 내의 값들을 만들어낼 수 있다. 이렇게되면 크기가 10000인 배열에서 정점의 간선 정보가 5개일때 메모리 낭비가 없다.

이전에 풀었던 예제와 문제도 똑같고 풀이도 똑같다 하지만 전 문제에서는 모두 배열로 체크하여 풀이했다면 이번에는 arrayList에 값을 담아 체크하므로 추후에 문제를 풀때 정점의 값이 크다면 이렇게 푸는게 훨씬 메모리 낭비도 적고 더 간편하게 풀 수 있을것 같다. 풀이에 대해 자세히 보고 싶다면 이전 문제 풀이를 참고하면 더 도움이 될거 같다. 이전 문제에서 배열에 대한 설명을 ArrayList로 대입하여 생각하면 쉽다.

그래프와 인접행렬 배열풀이