[프로그래머스] 등굣길 (DP)

문제 소개

오늘 풀었던 등굣길 - 프로그래머스 문제를 정리합니다.
이 문제는 격자 형태의 지도에서 특정 위치를 피해 최단경로의 개수를 구하는 DP 유형의 문제입니다.
핵심은 "오른쪽과 아래쪽으로만 이동", "물에 잠긴 지역은 지나갈 수 없음"이라는 조건입니다.

문제 링크: 등굣길 - 프로그래머스

---

문제 접근 방식

이 문제는 다음과 같은 방식으로 접근했습니다:

1. 최단 경로의 개수를 구해야 하므로 DP 테이블 생성
2. (1,1)부터 시작해서 오른쪽 또는 아래 방향으로 누적 경로 개수 계산
3. puddle 좌표는 -1로 마킹한 뒤 0으로 처리, 즉 해당 위치는 갈 수 없음
4. 각 칸은 위에서 온 경우 + 왼쪽에서 온 경우의 합으로 누적
5. 최종 목적지 (n, m)에 도달하는 경로의 수가 정답

---

해결 과정 및 코드

핵심 아이디어

1. board[y][x] 배열을 만들어 (1,1)부터 (n,m)까지 각 지점까지 올 수 있는 경우의 수를 누적
2. 물에 잠긴 지점은 -1로 마킹한 뒤, DP 계산 중에는 0으로 만들어 경로에 포함되지 않게 처리
3. 위쪽 (board[i-1][j])과 왼쪽 (board[i][j-1])에서 온 경로의 수를 더해 현재 위치의 값을 계산
4. 모듈로 연산(% 1_000_000_007)을 통해 수가 커지는 것을 방지

코드

시간 복잡도 : O(NM)

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int [][] board = new int[n+1][m+1];  // 1-based index 사용 (board[y][x])
        
        // 물에 잠긴 지역은 -1로 표시
        for (int [] puddle : puddles) {
            board[puddle[1]][puddle[0]] = -1;
        }

        board[1][1] = 1; // 시작 위치는 경로 수 1로 초기화

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (board[i][j] < 0) {
                    board[i][j] = 0;  // 물웅덩이는 경로 없음
                    continue;
                }
                // 윗 칸과 왼쪽 칸에서 온 경로 수를 더함
                board[i][j] += (board[i-1][j] + board[i][j-1]) % 1_000_000_007;
            }
        }

        return board[n][m];
    }
}