미로 속 쥐(Rat in a Maze) 문제 – 백트래킹으로 경로 찾기

문제 개요

이 문제에서는 N × N 크기의 미로가 주어집니다. 출발점은 항상 좌측 상단 칸이며, 도착점은 우측 하단 칸입니다. 미로에는 이동할 수 있는 칸과 막혀 있는 칸이 섞여 있고, 한 마리의 쥐가 출발점에서 도착점까지 이동할 때 경로를 완성할 수 있는지 판별해야 합니다. 경로가 존재한다면, 쥐가 따라갈 올바른 이동 경로를 표시하는 것이 목표입니다.

미로는 이진 행렬(binary matrix)로 표현됩니다. 값이 1인 칸은 이동 가능한 유효한 경로이고, 값이 0인 칸은 막혀 있는(블록된) 영역을 의미합니다.

참고: 쥐는 오른쪽 또는 아래쪽, 두 방향으로만 이동할 수 있습니다.

입력과 출력

입력:
알고리즘은 미로를 행렬 형태로 입력받습니다.
행렬에서 값 1은 자유롭게 이동할 수 있는 공간을, 0은 벽 또는 막힌 영역을 나타냅니다.


위 그림에서 좌측 상단의 원이 시작점, 우측 하단의 원이 도착점입니다.

출력:
쥐가 목적지에 도달한 경로를 확인할 수 있는 행렬을 출력합니다.

알고리즘

이 문제는 대표적인 백트래킹(backtracking) 기법으로 해결합니다. 쥐는 한 칸씩 이동하면서 경로를 표시하고, 막다른 길에 도달하면 이전 위치로 되돌아가(백트래킹) 다른 방향을 시도합니다.

isValid(x, y)

입력: 미로 내의 좌표 x와 y

출력: (x, y) 위치가 유효하면 true, 그렇지 않으면 false

Begin
    if x와 y가 범위 내에 있고 (x, y) 위치가 막혀 있지 않으면
        return true
    return false
End

solveRatMaze(x, y)

입력: 시작 좌표 x와 y

출력: 쥐가 목적지에 도달하기 위해 따라가야 할 경로, 경로가 없으면 false

Begin
    if (x, y)가 우측 하단 모서리라면
        해당 위치를 1로 표시
        return true
    if isValidPlace(x, y) = true 라면
        (x, y) 위치를 1로 표시
        if solveRatMaze(x+1, y) = true 라면   // 전진 방향 이동
            return true
        if solveRatMaze(x, y+1) = true 라면   // 아래쪽 방향 이동
            return true
        백트래킹 시 (x, y)를 0으로 되돌림
        return false
    return false
End

C++ 구현 예제

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

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

int sol[N][N];          // 미로 경로의 최종 해답이 저장되는 배열
void showPath() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}

bool isValidPlace(int x, int y) {   // 해당 위치가 미로 내부에 있고 값이 1인지 확인하는 함수
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;
    return false;
}

bool solveRatMaze(int x, int y) {
    if(x == N-1 && y == N-1) {      // (x, y)가 우측 하단 방인 경우
        sol[x][y] = 1;
        return true;
    }

    if(isValidPlace(x, y) == true) {    // (x, y)가 유효한 위치인지 확인
        sol[x][y] = 1;                  // 유효한 위치라면 1로 설정
        if (solveRatMaze(x+1, y) == true)   // 전진 방향으로 경로 탐색
            return true;
        if (solveRatMaze(x, y+1) == true)   // 전진 방향이 막혔으면 아래쪽 방향으로 진행
            return true;
        sol[x][y] = 0;                  // 두 방향 모두 막혔다면 경로가 없으므로 되돌림
        return false;
    }
    return false;
}

bool findSolution() {
    if(solveRatMaze(0, 0) == false) {
        cout << "There is no path";
        return false;
    }
    showPath();
    return true;
}

int main() {
    findSolution();
}

실행 결과

출력 행렬에서 값이 1인 칸들이 바로 쥐가 출발점(좌측 상단)에서 도착점(우측 하단)까지 이동한 실제 경로입니다. 만약 미로에 어떤 경로도 존재하지 않는다면, 프로그램은 "There is no path"라는 메시지를 출력합니다.

이 알고리즘의 시간 복잡도는 각 칸마다 두 방향을 시도하므로 최악의 경우 O(2^(N²))이며, 추가로 사용하는 sol 배열 때문에 공간 복잡도는 O(N²)입니다.