경로 탐색(인접행렬)

설명

방향그래프가 주어지면 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.*;

class Main{
	static int n, m, answer = 0;
	static int[][] graph;
	static int[] ch;
	public void DFS(int v) {
		if(v==n) {
			answer ++;
		}else {
			for(int i=1; i<=n; i++) {
				// v : 현재 정점
				if(graph[v][i] == 1 && ch[i]==0) {
					ch[i] = 1;
					DFS(i);
					ch[i] = 0;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Main T = new Main();
		Scanner in = new Scanner(System.in);
		// 정점의 갯수
		n=in.nextInt();
		// 간선의 갯수
		m=in.nextInt();
		// 인접행렬
		graph=new int[n+1][n+1];
		ch = new int[n+1];
		for(int i=0; i<m; i++) {
			int a = in.nextInt();
			int b = in.nextInt();
			// 방향값 1
			graph[a][b] = 1;
		}
		ch[1] = 1;
		T.DFS(1);
		System.out.println(answer);
	}
}