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

경로탐색 시 정점이 많아지면 ArrayList로 구현해야한다

설명

방향그래프가 주어지면 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 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 T = new Main();
		Scanner in = new Scanner(System.in);
		// 정점의 갯수
		n=in.nextInt();
		// 간선의 갯수
		m=in.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 = in.nextInt();
			int b = in.nextInt();
			graph.get(a).add(b);
		}
		ch[1] = 1;
		T.DFS(1);
		System.out.println(answer);
	}
	
}