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

문제 (경로탐색, 인접리스트)
총 정점수 n, 간선 수 m
m개 만큼의 간선의 수가 주어짐
1부터 n번까지 가는 경우의 수를 구하여라

• 인접행렬의 단점보완
  1에서 2,3,4가 인접되어 있으면
  1 -> 2, 3, 4를 리스트로
  2에서 1,3이 인접되어 있으면
  2 -> 1, 3을 리스트로
  ArrayList<ArrayList> graph

입력값
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5

결과값
6

import java.util.ArrayList;
import java.util.Scanner;

public class Main {


    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static int[] check;
    static int answer;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        check = new int[n + 1];

        answer = 0;
        check[1] = 1;
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();

            list.get(a).add(b);
        }

        DFS(1, n);
        System.out.println(answer);
    }

    private static void DFS(int node, int lastNode) {
        if (node == lastNode) {
            answer++;
        } else {
            for (int val : list.get(node)) {
                if (check[val] == 0) {
                    check[node] = 1;
                    DFS(val, lastNode);
                    check[node] = 0;
                }
            }
        }

    }

}