경로 탐색(인접행렬)

방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력한다.

해당 그래프에서 1번에서 5번 정점으로 가는 가지수를 구하시오.

 

첫째 줄에는 정점의 수 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

 

나의 입력

public class Main {
	static int n, m, answer=0; 
	static int[][] graph; 
	static int[] ck; 
	public int DFS(int x) {
		if(x==n)answer++; 
		else {
			for(int i=1; i<=n; i++) {
				if(graph[x][i]==1 && ck[i]==0) {
					ck[i]=1; 
					DFS(i);
					ck[i]=0; 
				}
			}
		}
		return 0; 
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in); 
		n = sc.nextInt(); //정점개수
		m = sc.nextInt(); //간선개수
		ck = new int[n+1]; // 체크배열
		graph = new int[n+1][n+1]; //[정점번호][정점번호]
		for(int i=0; i<m; i++) {
			int a = sc.nextInt(); 
			int b = sc.nextInt();
			graph[a][b] = 1; // a에서 b로 이동할 수 있다.   
		}
		ck[1]=1; // 출발점이 1이라서 1번 체크
		T.DFS(1); // 출발점부터 DFS시작 
		System.out.println(answer);
	}
}

 

1. 입력으로 주어진 정점의 개수 n과 간선의 개수 m을 입력받는다.
2. 그래프의 인접 행렬을 구성합니다. 각 간선 정보에 따라 인접 행렬의 해당 위치를 1로 설정한다.
3. 출발점인 1번 정점을 방문 체크하고 DFS를 호출한다.
4. DFS 함수에서는 현재 정점에서 연결된 모든 정점을 탐색하며 재귀적으로 호출한다. 만약 목표 정점에 도달하면 answer 값을 증가시킨다.
5. 모든 경로를 탐색한 후에는 최종적으로 answer 값을 출력다.

 

 

 

 

 

 

경로탐색 시 한번 방문한 곳은 다시 방문하지 않는다.