1. 경로 탐색(DFS)

    1번 문제   

 

 

---

    내가 풀이한 답   

 

 문제에 있는 예제는 다음과 같은 과정을 거친다. check 배열을 통해 이미 접근한 노드에 다시 접근하는 것을 방지하고 dfs 재귀 함수를 호출하였다.

 

 

 

//#include <bits/stdc++.h>
#include <iostream>
using namespace std;

int map[21][21], check[21], n, cnt=0;

void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i] == 1 && check[i] == 0){
				check[i] = 1;
				dfs(i);
				check[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][b] = 1;
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
	return 0;
}

 

 

 결과는 통과하였다.

 

 

---

 

    사이트의 답안   

 

<경로도 함께 출력하는 코드>
#include<stdio.h>	
int map[30][30], ch[30], cnt=0, n, path[30];
void DFS(int v, int L){
	int i, j;
	if(v==n){
		cnt++;
		for(j=0; j<L; j++){
			printf("%d ", path[j]);
		}
		puts("");
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]==1 && ch[i]==0){
				ch[i]=1;
				path[L]=i;
				DFS(i, L+1);
				ch[i]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, j, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	ch[1]=1;
	path[0]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}