65. 미로탐색(DFS)

문제

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

입력설명

첫 번째 줄부터 7*7 격자의 정보가 주어집니다.

출력설명

첫 번째 줄에 경로의 가지수를 출력한다.

입력예제

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

출력예제

8

---

#include <stdio.h>
#include <vector>
using namespace std;
int check[8][8], count=0;
vector<vector<int>> map(8, vector<int>(8));
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1}; // 12, 3, 6, 9 방향 

void DFS(int x, int y){
	int i, xx, yy;
	if(x==7 && y==7){
		count++;
	} 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 && check[xx][yy]==0){
				check[xx][yy] = 1;
				DFS(xx, yy);
				check[xx][yy] = 0;
			}
		}
	}
}

int main(){
	//freopen("input.txt", "rt", stdin);
	int m, i, j;
	
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	check[1][1] = 1;
	DFS(1, 1);
	printf("%d", count);
	
	return 0;
}

너무 어렵워 - ! ! www