66. 경로탐색(vector)

문제

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

입력설명

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

---

#include <stdio.h>
#include <vector>
using namespace std;
int n, check[30], count=0;
vector<int> map[30];

void DFS(int v){
	if(v == n){
		count++;
	} else {
		for(int i=0; i<map[v].size(); i++){
			if(check[map[v][i]] == 0){
				check[map[v][i]] = 1;
				DFS(map[v][i]);
				check[map[v][i]] = 0;
			}
		}
	}
}

int main(){
	//freopen("input.txt", "rt", stdin);
	int m, i, a, b;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a].push_back(b);
	}
	check[1] = 1;
	DFS(1);
	printf("%d", count);
	
	return 0;
}