c언어 미로찾기 (BPS)

#include <stdio.h>


#define SIZE 10 // 미로의 크기(SIZE * SIZE)
#define PATH 0 // 갈수있는 길
#define WALL 1 // 갈수없는 길 (벽)
#define VISIT 2 // 지나간 길 (최단거리)

int maze[SIZE][SIZE];  // 미로값 저장
int solution[SIZE][SIZE]; //최단거리 저장할 배열
void choicemaze();
void printmaze();
void printsolution();
int solve(int r, int c);



//입력받은 미로 1, 2


int maze1[SIZE][SIZE] = {
{0,0,1,1,0,1,1,1,0,0},
{1,0,0,0,0,0,0,1,0,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,0,0,1,1,0,1,1,1},
{0,0,1,0,1,1,0,0,0,0},
{1,1,1,0,1,1,1,1,1,1},
{1,1,0,0,0,1,0,0,0,0},
{0,0,0,1,0,1,0,1,1,1},
{1,0,1,1,0,0,0,0,0,1},
{1,0,1,1,0,1,1,1,0,0}
};

int maze2[SIZE][SIZE] = {
{0,1,0,0,0,1,0,0,0,0},
{0,1,0,1,0,0,0,1,1,1},
{0,0,0,1,0,1,0,0,0,1},
{1,0,1,1,0,1,1,1,0,0},
{0,0,1,1,0,1,1,1,1,1},
{1,1,0,0,0,1,0,0,0,1},
{0,0,0,1,0,0,0,1,0,0},
{1,1,0,1,1,0,1,1,1,1},
{1,0,0,1,0,0,0,0,0,0},
{0,0,1,1,0,1,1,0,1,0}
};


int main() {

    int i, j;

    while (1) {

    choicemaze(); // 미로 선택(1~2)
    printmaze(); //입력받은 미로 출력

    //최단거리 솔루션 모든값을 0으로 지정
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            solution[i][j] = 0;
        }
    }
    if (solve(0, 0))
        printsolution();
    else
        printf("이 미로는 출구가 없습니다.\n");

}
    return 0;
}



void choicemaze() {
    int num;
    int i, j;
    do {

        printf("미로를 입력하시오 1~2 : ");
        scanf_s("%d", &num);

        printf("%d 번 미로 \n ", num);
        switch (num) {
        case 1:
            for (i = 0; i < SIZE; i++) {
                for (j = 0; j < SIZE; j++) {
                    maze[i][j] = maze1[i][j];
                }
            }
            break;
        case 2:
            for (i = 0; i < SIZE; i++) {
                for (j = 0; j < SIZE; j++) {
                    maze[i][j] = maze2[i][j];
                }
            }
            break;
        default:
            printf("등록되지 않은 미로입니다. \n");
            break;
        }
    } while (!(num == 1 || num == 2));
    return;
 

}

//미로를 출력하는 함수
void printmaze() {
    int i, j;

    printf("------------입력받은 미로--------------\n\n");
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------------------\n\n");
}



// 최단거리 표시가된 미로 출력하는 함수
void printsolution() {
    int i, j;
    printf("----최단거리 미로를 표시합니다.-------\n\n");
    printf("0 갈수있는 길\n1 갈수없는 길 (벽)\n2 최단거리\n\n");
    for (i = 0; i < SIZE; i++) {
        for (j = 0; j < SIZE; j++) {
            printf("%d ", maze[i][j] + solution[i][j]);
        }
        printf("\n");
    }
    printf("--------------------------------------\n\n");
}


//최단거리 미로찾기 함수
int solve(int r, int c) {
    //출구에 도달하면 미로가 해결
    //출구에 해당하는 값(maze[SIZE-1][SIZE-1])
    if ((r == SIZE - 1) && (c == SIZE - 1)) {
        solution[r][c] = VISIT;
        return VISIT;
    }
    //지나간 길인지 확인
    //미로범위 안에서만 동작가능
    //solution[r][c] == 0 은 이미 방문하지 않은 길
    //maze[r][c] == 0 은 갈수있는 길
    if (r >= 0 && c >= 0 && r < SIZE && c < SIZE && solution[r][c] == 0 && maze[r][c] == 0 && maze[SIZE - 1][SIZE - 1] == 0) {
        //안전한 길이면 지나가시오(좌수법)
        solution[r][c] = VISIT;
        //아래로
        if (solve(r + 1, c))
            return VISIT;
        //오른쪽으로
        if (solve(r, c + 1))
            return VISIT;
        //위로
        if (solve(r - 1, c))
            return VISIT;
        //왼쪽으로
        if (solve(r, c - 1))
            return VISIT;
        //역으로
        solution[r][c] = 0;
        return 0;
    }
    return 0;
}