점프가 허용되는 미로 속 쥐 문제, 백트래킹으로 해결하기

미로 속 쥐(Rat in a Maze) 문제는 백트래킹(backtracking) 기법을 배울 때 가장 널리 알려진 대표 알고리즘 문제 중 하나입니다. 이 글에서는 여기에 약간의 변형을 더한, 점프가 허용되는 미로 문제를 살펴보겠습니다.

N×N 크기의 미로 M이 주어졌다고 가정합니다. 시작 지점은 좌측 상단 모서리인 M[0, 0]이고, 목적지는 우측 하단 모서리인 M[N-1, N-1]입니다. 쥐 한 마리를 시작 지점에 놓았을 때, 이 쥐가 목적지에 도달할 수 있는 경로를 찾는 것이 우리의 목표입니다. 일반적인 미로 문제와 달리, 이 변형 문제에서는 쥐가 점프를 할 수 있다는 점이 핵심입니다.

제약 조건

쥐는 오른쪽 또는 아래 방향으로만 이동할 수 있습니다.
셀의 값이 0이면 해당 칸은 막혀 있어 지나갈 수 없습니다.
0이 아닌 셀은 모두 유효한 경로입니다.
셀에 적힌 숫자는 그 위치에서 쥐가 최대 몇 칸까지 점프할 수 있는지를 나타냅니다.

알고리즘

핵심 아이디어는 백트래킹입니다. 현재 위치에서 가능한 모든 점프 거리를 하나씩 시도해 보고, 그 이동이 해답으로 이어지지 않으면 이전 상태로 되돌아가 다른 선택지를 탐색합니다.

ratInMaze 의사 코드

begin
    if 목적지에 도달했다면
        해답 행렬 출력
    else
        1. 현재 셀을 해답 행렬에 1로 표시한다.
        2. 앞으로 이동하거나 점프한다(해당 셀의 최대 점프 값 확인).
           이동 후 재귀적으로 그 이동이 해답으로 이어지는지 검사한다.
        3. 2단계의 이동이 올바르지 않다면 아래로 이동하여,
           그 이동이 해답으로 이어지는지 검사한다.
        4. 2단계와 3단계 어느 쪽도 해답이 아니라면,
           현재 셀을 다시 0으로 되돌린다(백트래킹).
    end if
end

C++ 구현 예제

#include <iostream>
#define N 4
using namespace std;

void dispSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}

bool isSafe(int maze[N][N], int x, int y) { // (x, y)가 유효한 좌표인지 확인
    // (x, y)가 미로 범위를 벗어나거나 막힌 칸이면 false 반환
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
        return true;
    return false;
}

bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1) { // 목적지에 도달하면 true 반환
        sol[x][y] = 1;
        return true;
    }
    if (isSafe(maze, x, y)) {
        sol[x][y] = 1; // 해답 행렬에 현재 셀을 1로 표시
        for (int i = 1; i <= maze[x][y] && i < N; i++) {
            if (ratMazeSolve(maze, x + i, y, sol)) // 아래 방향으로 i칸 점프
                return true;
            if (ratMazeSolve(maze, x, y + i, sol)) // 오른쪽 방향으로 i칸 점프
                return true;
        }
        sol[x][y] = 0; // 경로가 유효하지 않으면 다시 0으로 되돌림
        return false;
    }
    return false;
}

bool solveMaze(int maze[N][N]) {
    int sol[N][N] = { { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 },
                      { 0, 0, 0, 0 } };
    if (!ratMazeSolve(maze, 0, 0, sol)) {
        cout << "Solution doesn't exist"; // 해답이 존재하지 않음
        return false;
    }
    dispSolution(sol);
    return true;
}

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

실행 결과

결과 해석

해답 행렬에서 1로 표시된 칸이 쥐가 실제로 지나간 경로입니다. 위 예제에서 쥐의 이동 경로는 다음과 같습니다.

(0, 0)의 값이 2이므로 아래로 1칸 점프하여 (1, 0)으로 이동
(1, 0)의 값이 3이므로 오른쪽으로 3칸 점프하여 (1, 3)으로 이동
(1, 3) → (2, 3) → (3, 3): 오른쪽 끝 열을 따라 내려가 목적지 도착

이처럼 각 셀의 숫자를 활용해 점프 거리를 조절하면, 한 칸씩만 이동하는 일반적인 미로 문제보다 훨씬 적은 이동 횟수로 목적지에 도달할 수 있습니다. 다만 백트래킹 기반 탐색은 최악의 경우 지수형 시간 복잡도를 가질 수 있으므로, 미로의 크기가 커질수록 실행 시간이 급격히 늘어날 수 있다는 점을 유의해야 합니다.