[알고리즘/C] 미로찾기 경로탐색 (2차원 행렬 DFS: Depth First Search)

★ 이 미로찾기 경로탐색은 격자판에서 길찾기 알고리즘을 알아보는 2차원 행렬 DFS입니다.

방향 그래프상의 길찾기 알고리즘인 그래프 DFS는  아래 링크에서 확인바랍니다.

★ 또한 인접행렬과 경로탐색의 기초에 대해서도 아래 링크를 참고해주시기 바랍니다.

2022.12.05 - [Lang/알고리즘] - [알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search)

[알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search)

 

# 문제

7 * 7 격자판 미로를 탈출하는 경로의 가짓 수를 출력해야합니다.

출발점은 격자판의 (1,1) 지점이고,

도착점은 격자판의 (7,7) 지점입니다.

좌표의 값 1은 벽을 의미하고

좌표의 값 0은 길을 의미합니다.

이동은 상하좌우로만 가능합니다.

위 격자판에서 출발점에서 도착점으로 갈 수 있는 방법은 8가지입니다.

 

# 입력 예

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>

// am : 격자판
// ch : 해당 좌표로 이동했었는지 여부를 체크
// cnt : 도착 성공 횟수를 저장 
int am[9][9], ch[9][9], cnt;	 

// 가로 이동방향에 사용될 값 
int dr[4]={-1, 0, 0, 1};

// 세로 이동방향에 사용될 값 
int dc[4]={0, -1, 1, 0};

void D(int r, int c){
	int rr, cc;
	if(r==7 && c==7){
		cnt++;	// 좌표 (7,7)에 도착하면 성공횟수를 +1 합니다. 
	}
	else
	{
		// for문의 i=0 => 현재 좌표의 왼쪽 
		// for문의 i=1 => 현재 좌표의 위쪽 
		// for문의 i=3 => 현재 좌표의 아래쪽 
		// for문의 i=4 => 현재 좌표의 오른쪽 
		for(int i=0; i<4; i++){ 
			rr = r+dr[i];
			cc = c+dc[i];
			
			// 이동할 좌표가 격자판을 벗어나지 않도록 해주는 조건 
			if(rr==0||cc==0||rr==8||cc==8)continue;
			
			// 이동할 곳의 격자판이 길이고 &&
			// 이동할 곳이 가 본적 없는 곳이라면 
			if(am[rr][cc]==0 && ch[rr][cc]==0){
				
				// 이동할 곳에 가본 곳으로 체크하고 
				ch[rr][cc]=1;
				
				// 다음좌표로 재귀함수 탐색  
				D(rr, cc);
				
				// 탐색 종료 후 다음 탐색을 위해 체크 해제 
				ch[rr][cc]=0;
			}
		}
	}
	
}

int main(){
	freopen("input.txt", "rt", stdin);
	
	// 격자판 좌표 그대로 입력하기 위해 1 ~ 7 로 순회합니다. 
	for(int i=1; i<=7; i++){
		for(int j=1; j<=7; j++){
			scanf("%d", &am[i][j]);
		}
	}
	
    // 출발점(1,1)을 가본 곳으로 체크하고
    ch[1][1]=1;
    
    // 좌표 1,1을 시작으로 경로 탐색 시작
	D(1,1);
    
	printf("%d", cnt);
	return 0;
}