2. 미로탐색(DFS)

    2번 문제   

 

---

    내가 풀이한 답   

 

 문제에서는 7 X 7 형태로 정해져 있었지만 이해를 위해 3 X 3을 기준으로 생각을 해보았다. 한 좌표에서 위, 아래, 오른쪽, 왼쪽을 접근하려면 더 큰 인덱스가 필요했다. 그 결과 (N+2) X (N+2) 형태면 가능하다고 보았다. 아래 그림에서 도착점까지 갈 수 있는 방법은 총 두 가지고 그 중 한 가지의 시퀀스는 다음과 같다. →, ↓, ←, ↑ 순서로 탐색한다고 가정했다.

 

 

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

int map[9][9], check[9][9], cnt = 0;
int x[4] = {1, 0, -1, 0};
int y[4] = {0, 1, 0, -1};

void dfs(int a, int b){
	int xx, yy, i;
	if(a==7 && b==7) cnt++;
	else {
		for(i=0; i<4; i++){
			xx = x[i] + a;
			yy = y[i] + b;
			
			if(xx < 1 || yy < 1 || xx > 7 || yy > 7) continue;
			if(map[xx][yy] == 0 && check[xx][yy] == 0){
				check[xx][yy] = 1;
				dfs(xx, yy);
				check[xx][yy] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i, j;
	
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			cin >> map[i][j];		
		}
	}	
	
	check[1][1] = 1;
	dfs(1, 1);
	
	cout << cnt;
	
	return 0;
}

 

 

 결과는 통과하였다.

 

 

---

 

    사이트의 답안   

 

#include<stdio.h>
int map[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;

void DFS(int x, int y){	
	int xx, yy, i;
	if(x==7 && y==7){
		cnt++;
	}
	else{
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1 || xx>7 || yy<1 || 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(){
	freopen("input.txt", "r", stdin);
	int i, j;
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}