[42898] 등굣길

✔ 등굣길

[프로그래머스 42898]

문제 분석하기

동적계획법을 통해 각 집에서부터의 위치마다 경로를 저장

이후 최단경로를 가지는 갯수를 세서 반환

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i][j]는 (1, 1)인 집에서부터 (i, j)까지 갈 수 있는 최단 경로의 개수
2. 점화식을 구함
   • D[1][1] = 1
   • 오른쪽과 아래쪽으로만 움직일 수 있으므로
     왼쪽에서 오른쪽으로 이동하여 (i, j)에 도착했다면 D[i][j] += D[i][j - 1] % 1000000007
     위에서 아래쪽으로 이동하여 (i, j)에 도착했다면 D[i][j] += D[i - 1][j] % 1000000007
   • 이때 물이 잠긴 지역일 경우 계산하지 않음
3. 점화식으로 D 배열을 채운 후 학교 위치인 D[n][m] % 1000000007을 반환

슈도코드 작성하기

m, n(격자의 크기)
puddles(물이 잠긴 지역의 좌표)
mod(1000000007)
D(D[i][j]는 집에서부터 i번째 줄의 j번째까지의 최단 경로 횟수)
for(i -> puddles의 크기만큼) {
    D[puddles[i][1]][puddles[i][0]] = -1
}
D[1][1] = 1
for(i는 1 ~ n + 1) {
    for(j는 1 ~ m + 1) {
        if(물이 담긴 지역이라면) {
            continue
        }
        if(왼쪽의 최단경로 횟수가 0보다 크다면) {
            D[i][j] += D[i - 1][j] % mod
        }
        if(위쪽의 최단경로 횟수가 0보다 크다면) {
            D[i][j] += D[i][j - 1] % mod
        }
    }
    D[n][m] % mod 반환
}

코드 구현하기

/**
 * 42898) 등굣길
 */
public class K003_42898 {
    // m, n(격자의 크기)
    // puddles(물이 잠긴 지역의 좌표)
    public int solution(int m, int n, int[][] puddles) {
        // mod(1000000007)
        int mod = 1000000007;
        // D(D[i][j]는 집에서부터 i번째 줄의 j번째까지의 최단 경로 횟수)
        int[][] D = new int[n + 1][m + 1];
        // 물이 잠긴 지역은 지나갈 수 없으므로 최단 경로 횟수는 -1
        for (int i = 0; i < puddles.length; i++) {
            D[puddles[i][1]][puddles[i][0]] = -1;
        }
        // 집 위치 1
        D[1][1] = 1;
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < m + 1; j++) {
                // 물이 담긴 지역이라면
                if (D[i][j] == -1) {
                    continue;
                }
                // 왼쪽의 최단경로 횟수가 0보다 크다면
                if (D[i - 1][j] > 0) {
                    // 오른쪽으로 이동
                    D[i][j] += D[i - 1][j] % mod;
                }
                // 위쪽의 최단경로 횟수가 0보다 크다면
                if (D[i][j - 1] > 0) {
                    // 아래로 이동
                    D[i][j] += D[i][j - 1] % mod;
                }
            }
        }
        // D[n][m] % mod 반환
        return D[n][m] % mod;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        K003_42898 solution = new K003_42898();

        int m = 4;
        int n = 3;
        int[][] puddles = { { 2, 2 } };

        int result = solution.solution(m, n, puddles);

        System.out.println(result);
    }
}