행렬 확률 문제 – DFS 재귀로 N번 이동 후 행렬 안에 남을 확률 계산하기

문제 소개

이번 글에서는 행렬 확률(Matrix Probability) 문제를 다뤄보겠습니다. 크기가 m×n인 직사각형 행렬이 하나 주어져 있으며, 현재 칸에서는 왼쪽, 오른쪽, 위, 아래 네 방향으로 각각 동일한 확률(1/4)만큼 이동할 수 있습니다. 목표는 시작 위치 M[x, y]에서 정확히 N번 이동한 뒤에도 행렬 경계를 벗어나지 않고 행렬 안에 머무를 확률을 계산하는 것입니다.

접근 방법: DFS 기반 재귀 탐색

이 문제는 DFS(깊이 우선 탐색)와 유사한 방식으로 해결할 수 있습니다. 현재 위치에서 이동 가능한 네 방향을 재귀적으로 탐색하면서, 남은 이동 횟수를 하나씩 줄여 가며 확률을 누적합니다.

네 방향의 이동 확률이 모두 동일하기 때문에, 각 방향은 전체 확률의 0.25씩 기여합니다. 탐색 도중 행렬의 경계를 벗어나면 해당 경로는 유효하지 않으므로 0을 반환하고, N번의 이동을 모두 마쳤다면 그 경로는 성공한 것이므로 1을 반환합니다. 이렇게 얻은 값들을 모두 더하면 최종 확률을 구할 수 있습니다.

알고리즘

matProb(m, n, x, y, N)

시작
    만약 (x, y)가 행렬 경계 (m, n)을 벗어나면 0을 반환한다
    만약 N이 0이면 1을 반환한다
    prob := 0
    prob := prob + matProb(m, n, x-1, y, N-1) * 0.25   // 왼쪽 이동
    prob := prob + matProb(m, n, x+1, y, N-1) * 0.25   // 오른쪽 이동
    prob := prob + matProb(m, n, x, y+1, N-1) * 0.25   // 위 이동
    prob := prob + matProb(m, n, x, y-1, N-1) * 0.25   // 아래 이동
    prob를 반환한다
끝

C++ 구현 예제

#include<iostream>
using namespace std;

// (x, y)가 행렬 내부에 있는지 확인하는 함수
bool isSafe(int x, int y, int m, int n) {
    if(x >= 0 && x < m && y >= 0 && y < n){
        return true;
    }
    return false;
}

double matProb(int m, int n, int x, int y, int N) {
    if (!isSafe(x, y, m, n)) // 행렬 경계를 벗어난 경우
        return 0.0;
    if (N == 0) // N번의 이동을 모두 완료한 경우
        return 1.0;
    double probability = 0.0;
    probability += matProb(m, n, x - 1, y, N - 1) * 0.25; // 왼쪽 이동
    probability += matProb(m, n, x, y + 1, N - 1) * 0.25; // 위 이동
    probability += matProb(m, n, x + 1, y, N - 1) * 0.25; // 오른쪽 이동
    probability += matProb(m, n, x, y - 1, N - 1) * 0.25; // 아래 이동
    return probability;
}

int main() {
    int m = 7, n = 8;
    int x = 1, y = 1;
    int N = 4;
    cout << "Matrix Probability is " << matProb(m, n, x, y, N);
}

실행 결과

Matrix Probability is 0.664062

위 예제는 7×8 크기의 행렬에서 (1, 1) 위치에서 시작해 4번 이동한 경우입니다. 즉, 4번의 이동 후에도 행렬 경계를 벗어나지 않고 행렬 안에 남아 있을 확률이 약 0.664062, 대략 66.4%라는 의미입니다.

복잡도 분석

시간 복잡도: O(4^N) — 매 단계마다 네 방향으로 분기되므로, 이동 횟수 N에 대해 최대 4^N개의 경로를 탐색하게 됩니다.

공간 복잡도: O(N) — 재귀 호출의 깊이가 최대 N까지 이르므로 그만큼의 재귀 스택 공간이 필요합니다.