[알고리즘 문제]경로 탐색 - 인접행렬

▷ 문제

방향그래프가 주어지면 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 int[][] graph;
  static int[] ch;

  public int DFS(int v) {
    if(v == n){
      answer++;
    } else{
      for(int i=1; i<=n; i++){
        if(graph[v][i] == 1 && ch[i] == 0){
          ch[i] = 1;
          DFS(i);
          ch[i] = 0; // 백트랙킹 시 체크 해제
        }
      }
    }

    return answer;
  }

  public static void main(String[] args) {
    Main main = new Main();
    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;
    }
    kb.close();
    ch[1] = 1;

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

▷ 메모

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