Recursion을 이용한 미로찾기(C언어)

미로 찾기 문제 분석

 

미로 찾기 문제는 내가 직접 미로에 빠졌을 때 어떻게 탈출할 수 있을 지에 대한 관점으로 분석합니다. 먼저, 내가 서 있는 지점이 탈출구라면 탈출에 성공한 것이고 그 외에는 내가 지나온 길을 표시해서 다시 원점으로 돌아왔다면 그 길은 길이 아닌 것입니다. 만약 왔었던 길을 표시해주지 않으면 원점에서 동,서,남,북 방향으로 이동했을 때 그 지점들부터 다시 동,서,남,북으로 이동하면 왔던길을 다시 지나게 되어 무한루프가 발생하게 됩니다. 그래서 처음부터 내가 지날 수 있는 길들을 0으로 표시하고 벽들은 1로 표시합니다. 그리고 내가 지나간 지점들은 다 2로 표시해주고 그 길이 갈 수 없는 길이라면 3을 표시해줘서 다음에는 지나가지 않게 합니다.

 

미로 찾기 원리

 

 

먼저 이런 모양의 미로를 만듭니다. 회색은 벽이고 흰색은 길입니다.

먼저 동쪽으로 이동하는 경우만 생각합니다.

첫 번째 갈라지는 경우에서 남쪽으로 갈 때에 벽에 막히기 때문에 Blocked처리를 합니다.(더 이상 갈 수 없는 상태)

계속 나아가다 보면 또 벽에 부딪히게 됩니다.

그 부분 역시 Blocked처리를 합니다.

계속 이동해서 또 벽에 부딪히게 됩니다.

이 역시 벽에 부딪히고 처음에서 동쪽으로 출발한 쪽은 탈출구에 도달하는 길이 아니기 때문에 전체를 다 Blocked처리를 합니다. 그런 다음 처음부분에서 남쪽으로 이동하게 됩니다.

다른 막히는 길은 생략하고 탈출구로 향하는 길로 이동하는 경우만 봤을 때, 탈출구에 도달한다면 이동한 경로를 전부 다 Path(길)처리를 합니다. 만약 탈출구가 없다면 Path처리되는 곳은 없습니다.

 

 

 

미로 찾기 코드

 

#include <stdio.h>
 
const int N = 8;
const int PATHWAY_COLOUR = 0;//아직 한 번도 가보지 못한 cell
const int WALL_COLOUR = 1;//벽이라고 정해진 cell
const int BLOCKED_COLOUR = 3;//visited이며 출구까지의 경로가 있지 않음이 밝혀진 cell
const int PATH_COLOUR = 2;//visited이며 아직 출구로 가는 경로가 될 가능성이 있는 cell
int map[N][N] = {
    {0, 0, 0, 0, 0, 0, 0, 1},
    {0, 1, 1, 0, 1, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 0, 0, 1, 1, 0, 0},
    {0, 1, 1, 1, 0, 0, 1, 1},
    {0, 1, 0, 0, 0, 1, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 1},
    {0, 1, 1, 1, 0, 1, 0, 0}
};
 
int findMap(int x, int y) {
    if (x < 0 || y < 0 || x >= N || y >= N)
        return 0;
    else if (map[x][y] != PATHWAY_COLOUR)
        return 0;
    else if (x == N - 1 && y == N - 1) {
        map[x][y] = PATH_COLOUR;
        return 1;
    }
    else {
        map[x][y] = PATH_COLOUR;
        if (findMap(x - 1, y) || findMap(x, y + 1) || findMap(x + 1, y) || findMap(x, y - 1)) {
            return 1;
        }
        map[x][y] = BLOCKED_COLOUR;
        return 0;
    }
}
int main() {
    int i, j;
    printf("탈출 구 찾기 여부 : %d\n", findMap(0, 0));
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    return 0;
}