[Algorithms] Matrix Path Problem | 행렬 경로 문제

Matrix Path Problem

행렬 경로 문제

- \(n \; X \; n\) Matrix가 주어졌을 때, (\(n\)은 자연수)
  이 행렬의 왼쪽 위에서 시작해 한 칸씩 이동하며, 행렬의 오른쪽 아래까지 도달하되,
  이 과정에서 거쳐가는 행렬의 원소의 합이 가장 큰 경우는 어느 경우인지를 계산해야 하는 문제이다.
- 이 때, 이동방향은 오직 오른쪽, 아래쪽만 허용된다.
  (즉, 왼쪽, 위쪽, 대각선 이동은 허용되지 않는다.)

Example. Rule Violations and Compliance with Rules

규칙을 위반한 이동

 

유효한 이동

---

Mechanism (원리)

※ 이 문제의 답은 Optimal Substructure를 갖고 있으므로, Dynamic Programming (URL) 기법을 적용해 볼 수 있다.

[Algorithms] Dynamic Programming (DP) | 동적 프로그래밍

- 행렬의 왼쪽 위 원소 \((1, 1)\)에서 임의의 원소 \((i, j)\)까지 도달하는 경로에서
  \((i, j)\)에 도달하기 직전, 거칠수 있는 원소는 \((i-1, j)\) 혹은 \((i, j-1)\)이다.
- 즉, 둘 중 Cost가 더 높은 원소를 택하면 되고, 이러한 구조를 반복하여 정답을 찾아나가면 되므로,
  Optimal Substructure를 가졌음을 알 수 있다.
  (자신의 부분 문제에 대한 최적해를 자신의 최적해를 구성하는 데 사용하고 있다.)

---

Recursive Formula

\(C_{i, j} : \mathrm{Cost \; of \; Path \; from \;} (1, 1) \mathrm{\; to \;} (i, j)\)

\(C_{i, j} =
\begin{cases}
0 \; \qquad \qquad \qquad \qquad \qquad \qquad \mbox{(if } i=0 \mbox{ or} j=0)\\\\
m_{i, j} + \mathrm{max}\{C_{i, j-1}, C_{i-1, j}\} \qquad \mbox{(otherwise)}
\end{cases}\)   

- \(i\) 혹은 \(j\)가 0인 경우는 행렬의 경계를 의미하므로, 이에 대한 Cost는 0이어야 한다.

---

Implementation

1. Stupid Recursion (\(\Omega(2^n)\))

mat(i, j)
{
    if(i == 0 || j == 0)
        return 0;
    else
        return (m_ij + max(mat(i-1, j), mat(i, j-1));
}

Example. Recursion Tree for \(\texttt{mat(4, 4)}\)

- 즉, 문제가 Optimal Substructure를 갖고 있으나, 단순한 재귀로 구현했을 때,
  굉장한 비효율이 발생하므로 Dynamic Programming 기법을 적용하기에 알맞다.

---

2. Dynamic Programming with Loop (\(\Theta(n^2)\))
- 여기서 \(n\)은 행렬의 Row 혹은 Column의 개수이므로,
  사실상 이 알고리즘은 행렬의 원소의 개수에 선형으로 비례하는 시간이 소요된다.

mat(n)
{
    // Boundary Initialization
    for(int i = 0; i < n; i++)
        c[i][0] = 0;
    for(int j = 1; i < n; i++)
        c[0][j] = 0;
        
    // Computation for Optimal Solution
    for(int i = 1; i < n; i++)
        for(int j = 1; j < n; j++)
            c[i][j] = m_ij + max(c[i-1][j], c[i][j-1]);
    
    return c[n][n];    
}

---

Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)

Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)