+) 미로탐색(2차원 배열 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>

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 i, xx, yy;//xx는 앞으로 갈 격자를 파악하기 위한 것
    
    //도착한 경우
    if(x==7 && y==7){
        cnt++;
    } else {
        for(i=0;i<4;i++){
            xx = x + dx[i];
            yy = y + dy[i];
            
            //범위를 벗어나는 경우, continue
            if(xx<1 || xx>7 || yy<1 || yy>7) continue;
            
            //가려고 하는 곳이 갈 수 있는 곳이며, 지나가지 않았던 지점인 경우
            if(map[xx][yy]==0 && ch[xx][yy]==00){
                ch[xx][yy]=1;
                DFS(xx, yy);
                ch[xx][yy]=0;
            }
        }
    }
}

int main(){
    int i, j;
    for(i=1;i<=7;i++){
        for(j=1;j<=7;j++){
            scanf("%d", &map[i][j]);
        }
    }
    ch[1][1] = 1;//무조건 1행 1열부터 출발
    DFS(1, 1);
    printf("%d\n", cnt);
    
    
    return 0;
}

---

(참고 : IT 취업을 위한 알고리즘 문제풀이 (with C/C++))