[DAY81] Algorithm : Counting Shortest Paths

이번 포스트에서는 폭우로 물에 잠긴 격자에서 집(1, 1)에서 학교(m, n)까지 갈 수 있는 최단 경로의 개수를 구하는 문제를 다루었다. 최단 경로의 개수를 세는 문제는 전형적인 동적 계획법(DP) 문제로, 이전 지점의 경로 수를 합산하여 현재 지점의 경로 수를 계산했다. 특히 경로 개수가 매우 커질 수 있어 나머지 연산($\pmod{1,000,000,007}$)을 적용하고, 웅덩이(장애물) 지점은 경로 개수를 0으로 처리하는 것이 핵심이었다.

---

❓ 문제 분석

• 목표: 집 (1, 1)에서 학교 (m, n)까지 오른쪽과 아래쪽으로만 이동하여 갈 수 있는 최단 경로의 개수를 구한다. (결과를 $1,000,000,007$로 나눈 나머지 반환)
• 제약 조건: 격자 크기 $m, n \le 100$. (최대 $100 \times 100$ 격자이므로, $O(N^2)$ 또는 $O(N \cdot M)$의 시간 복잡도로 충분하다.)
• 핵심 키워드: "최단 경로의 개수", "격자(Grid)", "오른쪽과 아래쪽으로만 이동"

---

💡 풀이 설계

격자형 맵에서 한 방향으로만 이동하는 경우의 수는 동적 계획법 (Dynamic Programming, DP)을 적용하기 가장 좋은 형태이다.

1. 시도했던 접근 (First Attempt)

• 처음에는 단순히 재귀 함수를 이용해 $(i, j)$에서 $(m, n)$까지 가는 모든 경우의 수를 재귀적으로 탐색하는 DFS(Depth-First Search)를 고려했다.
• 하지만 $100 \times 100$ 격자에서 단순 DFS를 사용하면 중복 계산이 너무 많아져 시간 복잡도가 기하급수적으로 커지므로, 시간 초과가 발생할 것이 확실했다.

2. 최종 해결책 (Solution)

• DP 테이블 정의: $\text{DP}[i][j]$를 $(i, j)$ 좌표까지 도달하는 최단 경로의 개수로 정의했다.
• 점화식: 오른쪽(가로) 또는 아래쪽(세로)에서만 올 수 있으므로,
  $\text{DP}[i][j] = \text{DP}[i-1][j] + \text{DP}[i][j-1]$
• 웅덩이 처리: 물에 잠긴 지역은 경로의 개수를 0으로 설정하여, 해당 지점을 경유하는 모든 경로를 차단했다.
• 예상 시간 복잡도: 격자 크기가 $M \times N$일 때, 모든 칸을 한 번씩 순회하므로 $O(M \cdot N)$. (최대 $100 \times 100$이므로 매우 효율적이다.)
• 알고리즘 흐름:
  1. DP 테이블($\text{long long}, [n+1][m+1]$ 크기)을 0으로 초기화한다.
  2. 입력 받은 웅덩이 좌표를 DP 테이블에 특수 값(-1)으로 표시하여 구분한다.
  3. 시작 지점 $\text{DP}[1][1]$을 1로 초기화한다.
  4. 2중 for 루프를 돌며 $i=1 \to n, j=1 \to m$ 순서로 테이블을 채운다.
  5. $\text{DP}[i][j] = (\text{DP}[i-1][j] + \text{DP}[i][j-1]) \pmod{1000000007}$ 로 계산한다. (웅덩이는 0 취급)

---

💻 코드 구현

#include <string>
#include <vector>

using namespace std;

// 나머지 연산을 위한 상수 (1,000,000,007)
const int MOD = 1e9 + 7;

int solution(int m, int n, vector<vector<int>> puddles) {
    // DP 테이블 선언 (크기 : n+1 x m+1 크기)
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));

    // 물 웅덩이 위치를 테이블에 -1로 표시
    for (const auto& puddle : puddles) {
        dp[puddle[1]][puddle[0]] = -1; 
    }


    // DP 테이블 채우기 (i: 세로, j: 가로)
    for (int i = 1; i <= n; ++i) { 
        for (int j = 1; j <= m; ++j) { 
            
		    // 시작 지점 테이블 설정
            if (i == 1 && j == 1) {
                dp[1][1] = 1;
                continue;
            }

            // 현재 위치가 웅덩이인 경우 테이블 설정
            if (dp[i][j] == -1) {
                dp[i][j] = 0;
                continue;
            }
            

            // 위쪽(i-1)과 왼쪽(j-1)에서 오는 경로 수 합산
            // 인덱스 0 참조 시 0값이 더해짐
            long long up = dp[i - 1][j]; 
            long long left = dp[i][j - 1];
            
            // 덧셈 후 나머지 연산 적용 (오버플로우 방지)
            dp[i][j] = (up + left) % MOD;
        }
    }
    return dp[n][m];
}

---

🐛 시행착오 및 디버깅

• 문제점: DP 테이블을 int로 선언했을 때, 경로의 개수가 $2 \times 10^9$를 초과할 경우 오버플로우가 발생할 가능성이 있었다.
• 원인: $\text{DP}[i-1][j]$와 $\text{DP}[i][j-1]$이 모두 $10^9$ 근처일 때, 이 둘을 더한 값이 int의 최댓값($\approx 2.14 \times 10^9$)을 넘어서면 잘못된 결과가 나온다.
• 해결:
  1. DP 테이블의 자료형을 long long으로 변경했다.
  2. 점화식을 (up + left) % MOD 형태로 작성하여, 덧셈을 수행하는 과정에서 안정성을 확보했다.

---

✅ 오늘의 회고

항목	내용
유형	Dynamic Programming (DP) / Grid Pathfinding
체감 난이도	중 (DP의 기본을 이해하고 나머지 연산 및 웅덩이 처리만 주의하면 됨)
복잡도	시간: $O(M \cdot N)$, 공간: $O(M \cdot N)$
새로 배운 것	DP 문제에서 큰 수에 대한 나머지 연산을 할 때는 long long을 사용하여 합산 과정에서 오버플로우가 발생하지 않도록 방지하는 것이 중요하다는 것을 다시 한번 확인했다. 💡