미로 속의 쥐도 역추적을 활용하는 인기 있는 문제 중 하나입니다. 나
미로는 일부 세포가 차단된 2D 매트릭스입니다. 셀 중 하나는 시작해야 하는 소스 셀입니다. 그리고 또 다른 하나는 우리가 도달해야 하는 목적지입니다. 차단된 셀로 이동하지 않고 소스에서 목적지까지의 경로를 찾아야 합니다. 풀리지 않은 미로의 그림이 아래에 나와 있습니다.
이것이 솔루션입니다.
이 퍼즐을 풀기 위해 먼저 소스 셀에서 시작하여 경로가 막히지 않은 방향으로 이동합니다. 선택한 경로가 목적지에 도달하게 하면 퍼즐이 해결됩니다. 그렇지 않으면, 우리는 돌아와서 우리가 걸어온 길의 방향을 바꿉니다. 코드에서도 동일한 논리를 구현할 것입니다.
Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}
Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1 설명
먼저 미로를 나타내는 행렬을 만들고 행렬의 요소는 0 또는 1이 됩니다. 1은 차단된 셀을 나타내고 0은 이동할 수 있는 셀을 나타냅니다. 위에 표시된 미로의 행렬은 다음과 같습니다.
0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0
이제 솔루션을 저장할 동일한 차원의 행렬을 하나 더 만듭니다. 요소도 0 또는 1이 됩니다. 1은 경로에 있는 셀을 나타내고 나머지 셀은 0이 됩니다. 솔루션을 나타내는 행렬은 다음과 같습니다.
1 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1
따라서 이제 행렬이 생겼습니다. 다음으로 소스 셀에서 대상 셀까지의 경로를 찾고 수행할 단계는 다음과 같습니다.
-
현재 셀을 확인하고 목적지 셀이면 퍼즐이 풀립니다.
-
그렇지 않은 경우 아래쪽으로 이동하여 아래쪽 셀에서 이동할 수 있는지 확인합니다(셀에서 이동하려면 비어 있어야 하고 경로에 이미 존재하지 않아야 함).
-
거기로 이동할 수 있으면 다음 아래쪽 셀로 이동하는 경로를 계속 진행합니다.
-
그렇지 않은 경우 오른쪽 셀로 이동하려고 합니다. 그리고 막히거나 가져가면 위쪽으로 이동합니다.
-
마찬가지로 위로 이동할 수 없으면 왼쪽 셀로 이동합니다.
-
네 가지 이동(아래, 오른쪽, 위 또는 왼쪽) 중 어느 것도 가능하지 않은 경우 단순히 뒤로 이동하여 현재 경로를 변경합니다(역추적).
따라서 요약하면 현재 셀에서 다른 셀(아래, 오른쪽, 위, 왼쪽)로 이동하려고 시도하고 이동할 수 없으면 다시 돌아와서 경로 방향을 다른 셀로 변경하는 것입니다.
printsolution → 이 함수는 솔루션 매트릭스를 출력하는 것입니다.
solvemaze → 이것은 역추적 알고리즘을 구현하는 실제 함수입니다. 먼저 (r==SIZE-1) 및 (c==SIZE-1)인 경우 셀이 대상 셀인지 확인합니다. 그것이 목적지 세포라면 우리의 퍼즐은 이미 풀린 것입니다. 그렇지 않은 경우 이동 가능한 셀인지 여부를 확인합니다. 유효한 셀은 행렬에 있어야 합니다. 즉, 인덱스는 0에서 SIZE-1 사이여야 합니다. r>=0 &&c>=0 &&r예시
#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
int i,j;
for(i=0;i<SIZE;i++) {
for(j=0;j<SIZE;j++) {
printf("%d\t",solution[i][j]);
}
printf("\n\n");
}
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
//if destination is reached, maze is solved
//destination is the last cell(maze[SIZE-1][SIZE-1])
if((r==SIZE-1) && (c==SIZE-1) {
solution[r][c] = 1;
return 1;
}
//checking if we can visit in this cell or not
//the indices of the cell must be in (0,SIZE-1)
//and solution[r][c] == 0 is making sure that the cell is not already visited
//maze[r][c] == 0 is making sure that the cell is not blocked
if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
//if safe to visit then visit the cell
solution[r][c] = 1;
//going down
if(solvemaze(r+1, c))
return 1;
//going right
if(solvemaze(r, c+1))
return 1;
//going up
if(solvemaze(r-1, c))
return 1;
//going left
if(solvemaze(r, c-1))
return 1;
//backtracking
solution[r][c] = 0;
return 0;
}
return 0;
}
int main() {
//making all elements of the solution matrix 0
int i,j;
for(i=0; i<SIZE; i++) {
for(j=0; j<SIZE; j++) {
solution[i][j] = 0;
}
}
if (solvemaze(0,0))
printsolution();
else
printf("No solution\n");
return 0;
}