Backtracking | Rat in a Maze

읽기 전

• 해당 게시물은 작성자가 학습한 내용을 정리 및 요약 목적으로 작성되었으므로 오역 및 오개념이 있을 수 있습니다.
• 바로잡기 위한 의견을 제시해주시면 매우 감사하겠습니다.

Rat in Maze

왼쪽 위가 시작점은 N*N 이진 행렬이 주어졌다고 하자. 도착 지점은 오른쪽 아래이며 좌표로 표현하면 시작점: maze[0][0], 도착점: maze[N-1][N-1]이 된다. 쥐는 시작점에서 출발하여 도착점까지 가야 하는데 오직 아래 방향과 우측 방향으로만 이동할 수 있다. 주어진 이진 행렬에서 0은 막혀있는 블록, 1은 경로로 사용할 수 있는 블록을 의미한다. 그렇다면 쥐가 maze의 시작점에서 도착점까지 갈 수 있는 경로를 출력하자.

Backtracking

1. 0으로 채워진 경로 행렬을 생성한다.
2. 쥐의 좌표와 전체 지도, 경로를 기록할 행렬을 받는 재귀함수를 생성한다.
3. 만약 좌표가 맵을 벗어나거나 유효하지 않은 좌표라면 넘어간다.
4. 가능한 좌표일 경우 해당 좌표에 1을 체크하고 현재 좌표가 도착지점인지 검사한다. 만약 도착지점이라면 경로를 출력한다.
5. (i+1, j), (i, j+1) 좌표에 대해 계속 재귀 탐색을 진행한다.
6. 만약 이후 단계에 문제가 생기면 (i, j) 좌표를 다시 0으로 초기화한다.

C코드

#include <stdio.h>
#define N 4
// 메인 함수에 사용할 재귀문 사전 정의
bool solveMazeUtil(int x, int y, int sol[N][N], int maze[N][N]);

// 해답 도출 시 전체 경로 출력
void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            printf("%d ", sol[x][y]);
        }
        printf("\n");
    }
}

// 좌표가 제약조건을 만족하는 지 검사
int isSafe(int x, int y, int maze[N][N])
{
    // x, y가 맵을 벗어나는 지, 해당 좌표가 경로로 사용될 수 있는 지 검사
    return (0 <= x && x < N && 0 <= y && y < N && maze[x][y] == 1);
}

// 결과를 반환하는 함수
bool solveMaze(int maze[N][N])
{
    int sol[N][N]; // 경로 배열 선언

    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            sol[x][y] = 0; // 전체 경로 초기화
        }
    }

    // 만약 성립하는 경로가 존재하면
    if (solveMazeUtil(0, 0, sol, maze) == true)
    {
        printSolution(sol); // 전체 경로 출력
        return true;
    }
    else // 성립하는 경로가 없으면
    {
        printf("There's no Solution!"); // 답없음 출력
        return false;
    }
}

// 재귀함수 정의
bool solveMazeUtil(int x, int y, int sol[N][N], int maze[N][N])
{
    if (x == N-1 && y == N-1 && maze[x][y] == 1)
    { // 만약 끝점에 도달하였고 그 노드가 도착점이라면
        sol[x][y] = 1; // 도착점 좌표의 경로에 1 체크
        return true; // 탐색 종료
    }

    if (isSafe(x, y, maze)) // 해당 좌표가 안전하면
    {
        sol[x][y] = 1; // 경로에 사용되었음을 체크
        if (solveMazeUtil(x+1, y, sol, maze)) 
        { // 우측 이동 시 문제가 없다면 이전 단계에 true 반환
            return true;
        }
        else if (solveMazeUtil(x, y+1, sol, maze))
        { // 하단 이동 시 문제가 없다면 이전 단계에 true 반환
            return true;
        }
        else // 모든 방향을 시도했음에도 성립하는 경로가 없다면
        {
            sol[x][y] = 0; // backtracking
            return false; // 이전 단계에 false 반환
        }
    }
    return false; // 안전한 좌표 없다면 false 반환
}

int main()
{
    int maze[N][N] = { { 1, 0, 0, 0 }, 
                       { 1, 1, 0, 1 }, 
                       { 0, 1, 0, 0 }, 
                       { 1, 1, 1, 1 } }; 

    solveMaze(maze); 
    return 0; 
}

Python 코드

def printSolution(sol):
    for i in sol:
        for j in i:
            print(str(j) + " ", end = "") # 이쁘게 출력하기 위함
        print("") # 개행

def isSafe(x, y, maze): # 조건검사하는 함수
    return (0 <= x < N and 0 <= y < N and maze[x][y] == 1)

def solveMaze(maze):
    sol = [[0 for j in range(4)] for i in range(4)]

    if solveMazeUtil(0, 0, sol, maze) == False:
        print("There's no Solution!")
        return False
    else:
        printSolution(sol)
        return True

def solveMazeUtil(x, y, sol, maze):
    if x == N-1 and y == N-1 and maze[x][y] == 1:
        sol[x][y] = 1 # 탐색이 끝나면 도착지점에 1 표시 후 종료
        return True

    if isSafe(x, y, maze): # 탐색 좌표가 안전하면
        sol[x][y] = 1 # 체크
        if solveMazeUtil(x+1, y, sol, maze): 
            return True # 우측으로 이동 시 이후에도 문제 없으면 True
        elif solveMazeUtil(x, y+1, sol, maze):
            return True # 하단으로 이동 시 이후에도 문제 없으면 True
        else:
            sol[x][y] = 0 # backtracking
            return False # 이전 단계로 퇴각

maze = [ [1, 0, 0, 0], 
         [1, 1, 0, 1], 
         [0, 1, 1, 0], 
         [1, 1, 1, 1] ]
N = 4
solveMaze(maze)

C++ 코드

c++ 코드는 C 코드와 문법을 비교했을 때 출력문을 제외하고는 없어서 주석을 생략하였다.

#include <bits/stdc++.h>
using namespace std;
#define N 4

bool solveMazeUtil(int x, int y, int sol[N][N], int maze[N][N]);

void printSolution(int sol[N][N])
{
    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            cout << sol[x][y] << " ";
        }
        cout << endl;
    }
}

int isSafe(int x, int y, int maze[N][N])
{
    return (0 <= x < N && 0 <= y < N && maze[x][y] == 1);
}

bool solveMaze(int maze[N][N])
{
    int sol[N][N];

    for (int x = 0; x < N; x++)
    {
        for (int y = 0; y < N; y++)
        {
            sol[x][y] = 0;
        }
    }

    if (solveMazeUtil(0, 0, sol, maze))
    {
        printSolution(sol);
        return true;
    }
    else
    {
        cout << "There's no Solution" << endl;
        return false;
    }
}

bool solveMazeUtil(int x, int y, int sol[N][N], int maze[N][N])
{
    if (x == N-1 && y == N-1 && maze[x][y] == 1)
    {
        sol[x][y] = 1;
        return true;
    }

    if (isSafe(x, y, maze))
    {
        sol[x][y] = 1;
        if (solveMazeUtil(x+1, y, sol, maze))
        {
            return true;
        }
        else if (solveMazeUtil(x, y+1, sol, maze))
        {
            return true;
        }
        else
        {
            sol[x][y] = 0;
            return false;
        }
    }
    return false;
}

int main()
{
    int maze[N][N] = { { 1, 0, 0, 0 }, 
                       { 1, 1, 0, 1 }, 
                       { 0, 1, 0, 0 }, 
                       { 1, 1, 1, 1 } }; 

    solveMaze(maze); 
    return 0; 
}

참고자료

1. Rat in a Maze | Backtracking-2