3. 경로 탐색(DFS : 인접리스트 방법)

    3번 문제   

 

 

---

    내가 풀이한 답   

 

 논리적인 흐름은 바뀌지 않고 자료 구조만 바뀌었다. 기존에 이차원 배열이었던 것을 21개의 벡터로 선언하였고 방문 체크를 위한 일차원 배열도 21 크기의 벡터 하나를 선언하였다. 

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> map[21], check(21);
int n, cnt=0;
 
void dfs(int v){
	if(v==n) cnt++;
	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);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a].push_back(b);
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
 
	return 0;
}

 

 

 결과는 통과하였다.

 

 

---

 

    사이트의 답안   

 

#include<stdio.h>
#include<vector>
using namespace std;
int ch[30], cnt=0, n;		
vector<int> 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;
				DFS(map[v][i]);
				ch[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);
	}
	ch[1]=1;
	DFS(1);
	printf("%d\n", cnt);
	return 0;
}