C++로 미로에서 목적지까지 도달하는 경로의 수 세기

문제 소개

미로는 행 × 열(row × col) 크기의 2차원 행렬로 표현됩니다. 이때 장애물이 있는 칸은 -1로, 지나갈 수 있는 칸은 -1이 아닌 값으로 표시합니다. 목표는 시작점인 arr[0][0]에서 출발하여 마지막 칸인 arr[row-1][col-1]까지 도달하는 것입니다.

단, 이동은 아래 두 가지 방향만 허용됩니다.

오른쪽 이동: arr[i][j] → arr[i][j+1]
아래쪽 이동: arr[i][j] → arr[i+1][j]

예제로 이해하기

예제 1

입력: arr[row][col] = {{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}

출력: 미로에서 목적지에 도달하는 방법의 수: 1

설명:

        0    1   2
  0     0    0   0
  1    -1   -1   0
  2     0    0   0

가능한 경로는 다음과 같습니다.

(0,0) → (0,1) → (0,2) → (1,2) → (2,2)

예제 2

입력: arr[row][col] = {{0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}

출력: 미로에서 목적지에 도달하는 방법의 수: 2

설명:

        0    1   2   3
  0     0    0   0   0
  1    -1    0  -1   0
  2    -1    0  -1   0
  3     0    0   0   0

가능한 경로는 다음 두 가지입니다.

(0,0) → (0,1) → (1,1) → (2,1) → (3,1) → (3,2) → (3,3)
(0,0) → (0,1) → (0,2) → (0,3) → (1,3) → (2,3) → (3,3)

접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 칸에 "그 칸까지 도달할 수 있는 경로의 수"를 누적하여 저장하는 것입니다.

먼저 배열의 모든 0을 1로 변경합니다. 이는 "해당 칸까지 도달하는 기본 경로 1개"를 의미합니다.
배열을 다시 순회하면서 각 칸을 확인합니다.
장애물(-1)이 있는 칸은 무시합니다.
장애물이 없다면 위쪽 칸(i-1, j)과 왼쪽 칸(i, j-1)의 값을 확인합니다.
위쪽 또는 왼쪽 칸의 값이 0보다 크면 그 칸에서 현재 칸으로 이동할 수 있다는 뜻이므로, 해당 값을 현재 칸(i, j)에 더합니다.
순회가 끝나면 마지막 칸 arr[row-1][col-1]에 목적지까지 도달하는 총 경로의 수가 저장됩니다.

알고리즘 단계

입력 배열 arr[row][col]을 미로로 받습니다.
destination_maze(int arr[row][col]) 함수는 배열을 인자로 받아 목적지에 도달하는 방법의 수를 반환합니다.
첫 번째 칸 arr[0][0]이 막혀 있으면(-1) 도달 자체가 불가능하므로 0을 반환합니다.
가장 왼쪽 열을 위에서 아래로 순회하며 값이 0인 칸을 1로 설정합니다. 장애물을 만나면 반복을 중단하는데, 이는 장애물 아래 칸들은 위쪽에서 접근할 수 없기 때문입니다.
마찬가지로 첫 번째 행도 왼쪽에서 오른쪽으로 순회하며 값이 0인 칸을 1로 설정합니다.
이제 (1,1)부터 배열 전체를 순회합니다. arr[i][j]가 -1이면 건너뜁니다.
arr[i-1][j](위쪽 칸) 또는 arr[i][j-1](왼쪽 칸)이 0보다 크면 현재 칸으로 이동 가능한 것이므로, 그 값을 arr[i][j]에 더합니다.
순회가 끝나면 arr[row-1][col-1]이 곧 총 경로의 수입니다.
값이 0보다 크면 그대로 반환하고, 그렇지 않으면 0을 반환합니다.

C++ 구현 예제

#include<bits/stdc++.h>

using namespace std;
#define row 3
#define col 3

int destination_maze(int arr[row][col]) {
    if (arr[0][0] == -1) {
        return 0;
    }
    for (int i = 0; i < row; i++) {
        if (arr[i][0] == 0) {
            arr[i][0] = 1;
        } else {
            break;
        }
    }
    for (int i = 1; i < col; i++) {
        if (arr[0][i] == 0) {
            arr[0][i] = 1;
        } else {
            break;
        }
    }
    for (int i = 1; i < row; i++) {
        for (int j = 1; j < col; j++) {
            if (arr[i][j] == -1) {
                continue;
            }
            if (arr[i - 1][j] > 0) {
                arr[i][j] = (arr[i][j] + arr[i - 1][j]);
            }
            if (arr[i][j - 1] > 0) {
                arr[i][j] = (arr[i][j] + arr[i][j - 1]);
            }
        }
    }
    if (arr[row - 1][col - 1] > 0) {
        return arr[row - 1][col - 1];
    } else {
        return 0;
    }
}
int main() {
    int arr[row][col] = {
        {
            0,
            0,
            0
        },
        {
            -1,
            -1,
            0
        },
        {
            0,
            0,
            0
        }
    };
    cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
    return 0;
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

출력

Count of number of ways to reach destination in a Maze are: 1

복잡도 분석

시간 복잡도: O(row × col) — 배열의 모든 칸을 한 번씩 순회합니다.
공간 복잡도: O(1) — 별도의 추가 배열 없이 입력 배열 자체를 수정하여 사용하므로 메모리가 절약됩니다.