66. 경로 탐색(DFS : 인접리스트 )

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보가 주어진다.
▣ 출력설명
총 가지수를 출력한다.
▣ 입력예제 1
5 9
1 2
1 3
1 4
2 1
2 3
2 5
3 4
4 2
4 5
▣ 출력예제 1
6

#include
#include
using namespace std;
int n,ch[30],cnt=0;
vector map[30];
void DFS(int v){
int i;
if(v==n){
cnt++;
}
else {
for(i=0;i<map[v].size();i++){
if(ch[map[v][i]]==0){
ch[map[v][i]]=1; // i노드 방문 체크
DFS(map[v][i]);
ch[map[v][i]]=0; // 체크해제
}
}
}
}
int main() {

int i,a,b,m;
cin>> n>>m; //노드 와 간선 입력 
for(i=1;i<=m;i++){
	cin>>a>>b; 
	map[a].push_back(b); // 인접리스트 생성 
}
ch[1]=1; //1번노드에서 출발 체크 
DFS(1);
cout<<cnt;

return 0;

}

좋은 웹페이지 즐겨찾기