경로탐색(DFS, 인접리스트, ArrayList)

01 May 2023 in Algorithm on Java, Coding, Test

문제

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

12345 125 13425 1345 1425 145

총 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

해결방법

• 정점의 개수가 작을 때는 인접행렬로 푸는 것이 쉬우나, 개수가 많아지면 메모리 소비가 심해지고 비효율적.
• 따라서, 정점의 개수가 많을 때는 인접 리스트를 이용하여 해결한다.

코드

import java.util.*;

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

    public void DFS(int v) {
        if (v == n) answer++;
        else {
            // 원소를 계속 가져오면서 체크한다. 
            for (int nv : graph.get(v)) {
                // 방문 하지 않은 경우에만
                if (ch[nv] == 0) {
                    // 해당 원소 방문 처리 후
                    ch[nv] = 1;
                    // 다음 진행.
                    DFS(nv);
                    // 그리고 방문 해제 처리.
                    ch[nv] = 0;
                }
            }
        }
    }

    public static void main(String[] args) {
        Main.Main T = new Main.Main();
        Scanner kb = new Scanner(System.in);
        n = kb.nextInt();
        m = kb.nextInt();
        // 그래프를 ArrayList로 이중으로 구현하여 사용.
        graph = new ArrayList<ArrayList<Integer>>();
        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 = kb.nextInt();
            int b = kb.nextInt();
            graph.get(a).add(b);
        }
        ch[1] = 1;
        T.DFS(1);
        System.out.println(answer);
    }
}