[알고리즘 문제]경로 탐색 - 인접리스트

▷ 문제

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

▣ 입력설명
첫째 줄에는 정점의 수 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.*;

public 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 = new Main();
    Scanner kb = new Scanner(System.in);

    n = kb.nextInt();
    m = kb.nextInt();
    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);
    }
    kb.close();
    ch[1] = 1;

    main.DFS(1);
    System.out.println(answer);
  }
}

▷ 메모

• 위와 같은 경로 탐색은 인접 행렬보다는 인접 리스트를 통해 푸는 것이 효율적이다.