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;
}
Author And Source
이 문제에 관하여(66. 경로 탐색(DFS : 인접리스트 )), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kkangg/66.-경로-탐색DFS-인접리스트저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)