프로그래머스 | Python | DP:테뷸레이션 | 등굣길 (Lv.3)

https://school.programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스

📌 문제 분석

이 문제는 격자(Grid)에서 최단 경로 개수를 찾는 테뷸레이션(Tabulation, Bottom-Up 방식)을 사용하는 동적 계획법(DP) 문제입니다.

특정 위치(집)에서 출발하여 목표 위치(학교)까지 이동하는 경우의 수를 구해야 합니다.

✅ 핵심 요소:

1. 격자 이동: 오른쪽과 아래쪽으로만 이동 가능
2. 장애물 고려: 물웅덩이(puddles)가 있는 경우 해당 위치로 이동 불가
3. MOD 연산: 결과가 매우 클 수 있으므로 1,000,000,007로 나눈 나머지를 반환

---

📌 DP 접근 방식

1️⃣ DP 테이블 정의

• dp[i][j]: (i, j)까지 가는 경로의 개수
• 초기값: dp[1][1] = 1 (출발점)

---

2️⃣ 점화식

• 물웅덩이가 아닌 경우:
  • dp[i-1][j]: 위쪽에서 오는 경우
  • dp[i][j-1]: 왼쪽에서 오는 경우
• dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1_000_000_007
• 물웅덩이(puddles)인 경우:
  • dp[i][j] = 0 (해당 위치는 지나갈 수 없음)

---

📌 코드 구현

def solution(m, n, puddles):
    MOD = 1_000_000_007

    # DP 테이블 초기화 (1-indexed 사용)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # 시작점 초기화
    dp[1][1] = 1

    # 물웅덩이 위치를 -1로 표시
    for x, y in puddles:
        dp[y][x] = -1  # 좌표 변환 (문제는 (x, y), 배열은 (y, x))

    # DP 테이블 채우기
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 시작점이거나 물웅덩이면 건너뛴다
            if (i == 1 and j == 1) or dp[i][j] == -1:
                continue

            # 위쪽에서 오는 경우 (이동 가능하면)
            if dp[i - 1][j] != -1:
                dp[i][j] += dp[i - 1][j] % MOD

            # 왼쪽에서 오는 경우 (이동 가능하면)
            if dp[i][j - 1] != -1:
                dp[i][j] += dp[i][j - 1] % MOD

            # MOD 연산 적용
            dp[i][j] %= MOD

    return dp[n][m]  # 학교 위치의 최종 경로 개수 반환

---

📌 실행 예제

print(solution(4, 3, [[2, 2]]))  # 출력: 4

---

📌 실행 과정 (solution(4, 3, [[2,2]]))

초기 dp 테이블 (4x3 격자, puddles 반영)

1   1   1   1
1   -1  1   2
1    1  2   4

최종 결과: dp[3][4] = 4 → 학교까지 갈 수 있는 경로는 4가지!

---

📌 시간 복잡도 분석

• O(m × n) → 최대 100 × 100 = 10,000 연산 → 충분히 빠름

---

📌 핵심 요약

✅ DP를 이용해 격자의 경로 개수를 저장

✅ 물웅덩이(puddles)는 지나갈 수 없도록 0 처리

✅ MOD 연산(1,000,000,007)을 활용하여 큰 수 처리