[c++] 미로탐색, 경로탐색(DFS_인접리스트)

미로탐색

#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int map[30][30], n, m, ch[30][30], cnt=0;
int dx[4]={-1, 0, 1, 0};
int dy[4]={0, 1, 0, -1};
void DFS(int x, int y){
	int i, j, xx, yy;	
	if(x==7 && y==7) {
		cnt++;
		return;
	}
	else {
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1 || yy<1 || xx>7 || yy>7){
				continue;
			}	
			if(map[xx][yy]==0 && ch[xx][yy]==0){
				ch[xx][yy]=1;
				DFS(xx, yy);
				ch[xx][yy]=0;
			}				
			
		}
	}
}
int main() {
	int a, b, i, j;
	freopen("input.txt", "rt", stdin);
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &a);
			map[i][j] = a;
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d", cnt);
	return 0;
}

 

인접리스트

#include <iostream>
#include <vector>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int n, m, ch[30], cnt=0;
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() {
	int a, b, i;
	//freopen("input.txt", "rt", stdin);
	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", cnt);
	return 0;
}