C++ 미로 탐색: 모서리 셀에서 중앙 셀까지의 모든 경로 찾기

문제 개요

숫자로 채워진 정사각형 미로가 있다고 가정해 보겠습니다. 목표는 모서리 셀에서 출발하여 중앙 셀에 도달하는 모든 경로를 찾는 것입니다.

이동 규칙은 간단합니다. 현재 셀의 값을 n이라 할 때, 상·하·좌·우 네 방향 중 하나를 선택해 정확히 n칸 이동해야 합니다. 즉, 셀 [i, j]에서 n은 해당 셀의 값이며, 다음 네 위치로만 이동할 수 있습니다.

• [i+n, j] — 아래로 n칸
• [i-n, j] — 위로 n칸
• [i, j+n] — 오른쪽으로 n칸
• [i, j-n] — 왼쪽으로 n칸

미로를 벗어나는 이동은 허용되지 않으며, 이미 방문한 셀을 다시 거치는 것도 금지됩니다.

입력 예시

다음과 같은 9×9 크기의 미로가 입력으로 주어진다고 해봅시다.

이 경우 프로그램은 아래와 같은 경로들을 출력합니다.

• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→MIDDLE
• (8, 8)→(7, 8)→(4, 8)→(4, 4)→MIDDLE

풀이 접근 방식

이 문제는 백트래킹(backtracking) 기법으로 해결할 수 있습니다. 핵심 아이디어는 네 개의 모서리에서 각각 탐색을 시작하고, 더 이상 진행할 수 없거나 중앙에 도달했을 때 이전 상태로 되돌아가 다른 방향을 시도하는 것입니다. 전체 절차는 다음과 같습니다.

1. 미로의 크기를 N := 9로 설정합니다.
2. is_ok() 함수를 정의합니다. 방문한 좌표의 집합(visited)과 좌표(pt)를 인자로 받아, pt의 행과 열이 모두 0 이상 N 미만 범위 안에 있고 visited에 포함되어 있지 않으면 true를 반환합니다.
3. 행 이동 방향 배열 dir_row := {-1, 1, 0, 0}을 정의합니다.
4. 열 이동 방향 배열 dir_col := {0, 0, -1, 1}을 정의합니다.
5. 탐색을 시작할 네 모서리의 행 좌표 배열 row := {0, 0, N-1, N-1}을 정의합니다.
6. 탐색을 시작할 네 모서리의 열 좌표 배열 col := {0, N-1, 0, N-1}을 정의합니다.
7. solve() 함수를 정의합니다. 이 함수는 미로(maze), 현재까지의 경로(path), 방문 집합(visited), 현재 좌표(curr)를 인자로 받습니다.
   • curr의 행과 열이 모두 N/2와 같다면, 즉 중앙 셀에 도달했다면 지금까지의 경로를 출력하고 함수를 종료합니다.
   • i를 0부터 3까지 반복하면서 다음을 수행합니다.
     • n := 현재 셀의 값 maze[curr.first][curr.second]
     • x := curr.first + dir_row[i] × n
     • y := curr.second + dir_col[i] × n
     • next := (x, y) 좌표 쌍 생성
     • is_ok(visited, next)가 참이면:
       • next를 visited에 삽입
       • path의 끝에 next 추가
       • solve(maze, path, visited, next) 재귀 호출
       • path의 마지막 요소 제거 (백트래킹)
       • visited에서 next 제거 (백트래킹)
8. main 함수에서는 다음을 수행합니다.
   • 방문 좌표를 저장할 집합 visited를 생성합니다.
   • 네 개의 모서리에 대해 반복하면서:
     • x := row[i], y := col[i]
     • pt := (x, y) 좌표 쌍 생성
     • visited에 pt를 삽입하고 path의 끝에 pt를 추가
     • solve(maze, path, visited, pt) 호출
     • path의 마지막 요소 제거 및 visited에서 pt 제거 (백트래킹)

재귀 호출이 반환된 후 경로와 방문 기록을 되돌리는 과정이 바로 백트래킹의 핵심입니다. 이를 통해 같은 셀을 두 번 방문하지 않으면서 가능한 모든 경로를 빠짐없이 탐색할 수 있습니다.

C++ 구현 예시

아래 구현 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
    return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
    for (auto it = path.begin(); it != path.end(); it++)
    cout << "(" << it->first << ", " << it->second << ")->";
    cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
    if (curr.first == N / 2 && curr.second == N / 2) {
        display_path(path);
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int n = maze[curr.first][curr.second];
        int x = curr.first + dir_row[i]*n;
        int y = curr.second + dir_col[i]*n;
        pair<int, int> next = make_pair(x, y);
        if (is_ok(visited, next)) {
            visited.insert(next);
            path.push_back(next);
            solve(maze, path, visited, next);
            path.pop_back();
            visited.erase(next);
        }
    }
}
void search_path(int maze[N][N]) {
    list<pair<int, int> > path;
    set<pair<int, int> > visited;
    for (int i = 0; i < 4; ++i) {
        int x = row[i];
        int y = col[i];
        pair<int, int> pt = make_pair(x, y);
        visited.insert(pt);
        path.push_back(pt);
        solve(maze, path, visited, pt);
        path.pop_back();
        visited.erase(pt);
    }
}
int main() {
    int maze[N][N] = {
        {3, 4, 4, 4, 7, 3, 4, 6, 3},
        {6, 7, 5, 6, 6, 2, 6, 6, 2},
        {3, 3, 4, 3, 2, 5, 4, 7, 2},
        {6, 5, 5, 1, 2, 3, 6, 5, 6},
        {3, 3, 4, 3, 0, 1, 4, 3, 4},
        {3, 5, 4, 3, 2, 1, 3, 3, 5},
        {3, 5, 4, 3, 2, 6, 4, 4, 3},
        {3, 5, 1, 3, 7, 5, 3, 6, 3},
        {6, 2, 4, 3, 4, 5, 4, 5, 1}
    };
    search_path(maze);
}

입력

{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}}

출력

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE