12. 경로 탐색(인접행렬) DFS

 

설명

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 6가지.

 

 

 

풀이

1. dfs문제 풀때는 static int 사용하는게 좋다.

정답같은걸 출력할때 재귀돌면서 계속 증가시켜야 되기 때문에...

 

2. 만약 그래프에서 1이고 check배열에서 아직 체킹이 안됐으면

ch[i]=1로 만들고

DFS실행

그리고 끝나면 다시 배열을 0으로 만들어준다.

import java.util.*;
class Main {
	static int n, m;
	static int[][] graph;
	static int[] ch;
	static int answer;
	
	public int DFS(int v){
		
		if(n==v) {
			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 T = 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;
		}
		ch[1]=1;
		System.out.println(T.DFS(1));
	
	}	
}