미로 속의 쥐(Rat in a Maze) 문제 – 백트래킹으로 푸는 C 프로그램

미로 속의 쥐(Rat in a Maze)는 백트래킹(backtracking) 기법을 활용하는 대표적인 알고리즘 문제 중 하나입니다.

미로는 일부 칸이 막혀 있는 2차원 행렬입니다. 행렬에는 출발점 역할을 하는 출발 셀(source cell)과 도착해야 하는 목적지 셀(destination cell)이 하나씩 존재하며, 우리가 해야 할 일은 막힌 칸에 들어가지 않으면서 출발점에서 목적지까지 가는 경로를 찾는 것입니다. 아래는 아직 풀리지 않은 미로의 모습입니다.

그리고 이것이 그 해답입니다.

미로 속의 쥐(Rat in a Maze) 문제 – 백트래킹으로 푸는 C 프로그램

접근 방식

이 퍼즐을 풀려면 먼저 출발 셀에서 시작해 경로가 막히지 않은 방향으로 이동합니다. 선택한 경로가 목적지에 도달하면 퍼즐은 해결된 것이고, 그렇지 않다면 뒤로 물러나 이동 방향을 바꿉니다. 우리는 이 논리를 코드에 그대로 구현하게 됩니다.

입력:
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}}

출력:
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은 막힌 칸(blocked cell), 0은 이동 가능한 칸을 의미합니다. 앞서 본 미로의 행렬은 다음과 같습니다.

다음으로 같은 크기의 행렬을 하나 더 만들어 해답을 저장합니다. 이 행렬의 원소 역시 0 또는 1이며, 1은 실제로 지나간 경로의 칸을, 나머지 칸은 0으로 표시합니다. 해답 행렬은 다음과 같습니다.

이제 출발 셀에서 목적지 셀까지의 경로를 찾으면 됩니다. 탐색 절차는 다음과 같습니다.

현재 셀이 목적지 셀인지 확인합니다. 목적지라면 퍼즐이 해결된 것입니다.
아니라면 아래쪽 칸으로 이동을 시도합니다. 어떤 칸으로 이동하려면 그 칸이 비어 있어야 하고, 이미 경로에 포함되어 있지 않아야 합니다.
이동할 수 있다면 그 경로를 따라 계속 진행합니다.
아래쪽이 막혀 있다면 오른쪽 칸으로 이동을 시도하고, 오른쪽도 막혀 있거나 이미 지나온 길이라면 위쪽으로 이동합니다.
위쪽으로도 이동할 수 없다면 마지막으로 왼쪽 칸으로 이동합니다.
네 방향(아래, 오른쪽, 위, 왼쪽) 모두 이동이 불가능하다면 뒤로 물러나 경로의 방향을 변경합니다. 이것이 바로 백트래킹입니다.

요약하면, 현재 셀에서 네 방향의 인접한 셀로 이동을 시도하고, 어떤 이동도 불가능하면 한 칸 뒤로 돌아가 다른 방향의 경로를 탐색하는 방식입니다.

핵심 함수 살펴보기

printsolution → 해답 행렬을 화면에 출력하는 역할만 담당하는 함수입니다.

solvemaze → 백트래킹 알고리즘이 실제로 구현되는 핵심 함수입니다. 먼저 조건 (r==SIZE-1) && (c==SIZE-1)을 통해 현재 셀이 목적지 셀인지 확인합니다. 목적지라면 퍼즐은 이미 해결된 상태입니다. 아니라면 해당 셀이 유효한 이동 대상인지 검사하는데, 유효한 셀이 되려면 다음 세 가지 조건을 모두 만족해야 합니다.

행렬 범위 안에 있어야 합니다. 즉 인덱스가 0 이상 SIZE-1 이하여야 합니다(r>=0 && c>=0 && r<SIZE && c<SIZE).
막힌 칸이 아니어야 합니다(maze[r][c] == 0).
이미 경로에 포함되지 않았어야 합니다(solution[r][c] == 0).

세 조건을 통과하면 해당 칸을 경로에 추가하고 다음 셀로 이동합니다. 우선 아래쪽 칸(solveMaze(r+1, c))을 시도하고, 해답을 찾지 못하면 오른쪽, 이어서 위쪽, 왼쪽 순서로 탐색합니다. 네 방향 모두 실패하면 현재 칸을 경로에서 제거하고(solution[r][c] = 0) 다른 경로를 찾아 되돌아갑니다.

전체 예제 코드

#include <iostream>
using namespace std;
#define SIZE 5
//미로 문제
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}
};
//해답을 저장할 행렬
int solution[SIZE][SIZE];
//해답 행렬을 출력하는 함수
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");
   }
}
//백트래킹으로 미로를 푸는 함수
int solvemaze(int r, int c) {
   //목적지에 도달하면 미로는 해결됨
   //목적지는 마지막 칸(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1)) {
      solution[r][c] = 1;
      return 1;
   }
   //이 칸을 방문할 수 있는지 확인
   //칸의 인덱스는 반드시 (0, SIZE-1) 범위 안에 있어야 하며,
   //solution[r][c] == 0은 아직 방문하지 않은 칸임을 보장하고
   //maze[r][c] == 0은 막히지 않은 칸임을 보장
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      //안전하다면 해당 칸을 방문
      solution[r][c] = 1;
      //아래로 이동
      if(solvemaze(r+1, c))
         return 1;
      //오른쪽으로 이동
      if(solvemaze(r, c+1))
         return 1;
      //위로 이동
      if(solvemaze(r-1, c))
         return 1;
      //왼쪽으로 이동
      if(solvemaze(r, c-1))
         return 1;
      //백트래킹
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   //solution 행렬의 모든 원소를 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;
}

이 코드는 (0, 0)에서 출발해 재귀적으로 네 방향을 탐색하며, 경로가 막히면 스스로 되돌아가 다른 길을 찾는 백트래킹의 동작 원리를 명확하게 보여줍니다. 해답이 존재하면 solution 행렬에 1로 표시된 경로가 출력되고, 존재하지 않으면 "No solution" 메시지가 출력됩니다.