이번 글에서는 n×n 격자 미로에서 출발하는 '미로의 쥐(Rat in a Maze)' 문제의 변형 버전을 다룹니다. 쥐는 격자의 왼쪽 위 모서리에 위치해 있으며, 오른쪽(앞쪽) 또는 아래쪽으로만 이동할 수 있습니다. 또한 이동하려는 칸의 값이 0이 아닌 경우에만 그 칸을 밟을 수 있습니다.
이 변형 문제의 핵심은 여러 칸 점프(multiple jumps)가 허용된다는 점입니다. 현재 칸에 적힌 숫자가 곧 쥐가 한 번에 점프할 수 있는 최대 거리를 의미합니다. 예를 들어 현재 칸의 값이 3이라면, 쥐는 오른쪽 또는 아래 방향으로 1칸, 2칸, 3칸 중 원하는 만큼 점프할 수 있습니다. 우리의 목표는 쥐가 격자의 오른쪽 아래 모서리까지 도달할 수 있는지 판단하고, 가능하다면 그 경로를 출력하는 것입니다.
입력 및 출력 예시
입력 : { {1, 1, 1, 1},
{2, 0, 0, 2},
{3, 1, 0, 0},
{0, 0, 0, 1}
}
출력 : { {1, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0},
{0, 0, 0, 1}
}
입력 : {
{2, 1, 0, 0},
{2, 0, 0, 1},
{0, 1, 0, 1},
{0, 0, 0, 1}
}
출력 : 경로가 존재하지 않음문제 해결 접근 방식
이 문제는 백트래킹(backtracking) 기법을 사용하여 해결할 수 있습니다. 백트래킹이란 가능한 모든 경로를 하나씩 탐색해 보되, 막다른 길에 도달하면 이전 분기점으로 되돌아가 다른 경로를 시도하는 방법입니다.
구체적인 동작 과정은 다음과 같습니다.
1. 현재 칸에서 점프 가능한 모든 거리(1부터 해당 칸의 값까지)와 두 방향(오른쪽, 아래)을 조합하여 재귀적으로 탐색합니다.
2. 어떤 경로라도 목적지(오른쪽 아래 모서리)에 도달하면 true를 반환하고, 지나온 경로를 결과 배열에 1로 표시합니다.
3. 모든 경로를 탐색했는데도 목적지에 도달하지 못하면 "경로가 존재하지 않음"을 출력합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
#define N 4 // 격자의 크기
// 경로를 찾기 위한 재귀 함수
bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]){
// 목적지에 도달하면 true를 반환하고 해당 칸을 1로 표시
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
// 현재 위치가 격자 범위 안에 있고, 값이 0이 아니라면 진행
if (x >= 0 && y >= 0 && x < N && y < N && maze[x][y]) {
sol[x][y] = 1; // 현재 칸을 경로에 포함
// maze[x][y]는 점프할 수 있는 칸 수를 의미하므로,
// 모든 점프 거리와 방향을 확인
for (int i = 1; i <= maze[x][y] && i < N; i++) {
if (solveMaze(maze, x + i, y, sol) == true) // 오른쪽으로 점프
return true;
if (solveMaze(maze, x, y + i, sol) == true) // 아래로 점프
return true;
}
// 어느 방향으로도 목적지에 도달하지 못하면
// 현재 칸은 유효한 경로가 아니므로 다시 0으로 되돌림
sol[x][y] = 0;
return false;
}
return false;
}
int main(){
int maze[N][N] = { { 2, 1, 0, 0 }, { 3, 0, 0, 1 },{ 0, 1, 0, 1 },
{ 0, 0, 0, 1 } };
int sol[N][N];
memset(sol, 0, sizeof(sol));
if(solveMaze(maze, 0, 0, sol)){
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++)
cout << sol[i][j] << " ";
cout << "\n";
}
}
else
cout << "경로가 존재하지 않습니다\n";
return 0;
}실행 결과
1 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1
코드 동작 원리 상세 설명
위 코드는 현재 칸에서 만들 수 있는 모든 경로를 하나씩 검사하면서, 탐색 중인 경로의 칸들을 결과 배열에 1로 표시해 나갑니다. 탐색이 막다른 길에 도달하면 그 지점이 목적지인지 먼저 확인합니다. 목적지가 아니라면 백트래킹을 수행하는데, 이때 해당 경로는 유효하지 않으므로 지나왔던 칸들을 다시 0으로 되돌립니다. 이러한 과정을 반복하며 가능한 모든 경로를 체계적으로 탐색하는 것이 이 코드의 핵심 동작 방식입니다.
시간 복잡도 측면에서 보면, 각 칸에서 최대 N가지의 점프 거리와 2개의 방향을 고려하므로 최악의 경우 지수 시간이 소요될 수 있습니다. 하지만 백트래킹은 불가능한 경로를 조기에 가지치기(pruning)하기 때문에 실제로는 전체 경우의 수를 모두 탐색하지 않고도 답을 찾을 수 있는 경우가 많습니다.
마무리
이 튜토리얼에서는 여러 칸 점프가 허용되는 미로의 쥐 문제를 백트래킹 알고리즘으로 해결하는 방법을 살펴보았습니다. 문제의 정의, 전체 접근 방식, 그리고 완성된 C++ 프로그램까지 함께 학습했습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있으니, 개념을 익힌 후 다른 언어로도 직접 작성해 보시길 권장합니다. 이 글이 여러분의 알고리즘 학습에 도움이 되기를 바랍니다.