미로탐색(DFS) / c / 제한시간 없음

▣ 문제

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

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int map[8][8];
int visit[8][8] = { 0 };
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int cnt = 0;
int i, j;

int check(int y, int x) {
	if (x > 0 && x <= 7 && y > 0 && y <= 7) return 1;
	else return 0;
}

void dfs(int y, int x) {
	if (x == 7 && y == 7) {
		cnt++;
	}
	else {
		for (i = 0; i < 4; i++) {
			if (map[y + dy[i]][x + dx[i]] == 0 && check(y + dy[i], x + dx[i]) == 1 && visit[y + dy[i]][x + dx[i]] == 0) {
				visit[y + dy[i]][x + dx[i]] = 1;
				dfs(y + dy[i], x + dx[i]);
				visit[y + dy[i]][x + dx[i]] = 0;
			}
			else continue;
		}
	}
}

int main() {

	for (i = 1; i <= 7; i++) {
		for (j = 1; j <= 7; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	visit[1][1] = 1;
	dfs(1, 1);
	printf("%d\n", cnt);
	return 0;
}

check 함수는 다음 x,y 좌표가 경계선을 벗어나는지 확인하는함수이다.

 

경로찾기랑 똑같이 코드 진행이 되는것같은데 어디서 틀린지 모르겠음

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int map[8][8];
int visit[8][8] = { 0 };
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int cnt = 0;

int check(int y, int x) {
	if (x > 0 && x <= 7 && y > 0 && y <= 7) return 1;
	else return 0;
}

void dfs(int y, int x) {
	int i;
	if (x == 7 && y == 7) {
		cnt++;
	}
	else {
		for (i = 0; i < 4; i++) {
			if (map[y + dy[i]][x + dx[i]] == 0 && check(y + dy[i], x + dx[i]) == 1 && visit[y + dy[i]][x + dx[i]] == 0) {
				visit[y + dy[i]][x + dx[i]] = 1;
				dfs(y + dy[i], x + dx[i]);
				visit[y + dy[i]][x + dx[i]] = 0;
			}
			else continue;
		}
	}
}

int main() {
	int i, j;
	for (i = 1; i <= 7; i++) {
		for (j = 1; j <= 7; j++) {
			scanf("%d", &map[i][j]);
		}
	}
	visit[1][1] = 1;
	dfs(1, 1);
	printf("%d\n", cnt);

	return 0;
}

****중요한 개념****

 

나랑 비슷한 코드를 만든 사람의 질문에 대한 답변 :

 

"재귀함수는 자신의 매개변수와 지역변수를 스택프레임에 저장하고 컨트롤합니다. 재귀함수를 사용해 백트랙킹을 하려면 컨트롤 변수들의 재귀함수의 지역변수이어야 합니다."

 

내 코드의 문제는 i,j가 쓰기 편하게 전역변수로 잡았는데 이때문에 문제가 생긴듯함.

 

.

 

정말 생각지 못한 중요한 개념 나옴