[프로그래머스 JAVA] 42898. 등굣길

문제 링크

---

프로그래머스

접근 방법

---

집에서 학교까지 오른쪽과 아래쪽으로만 이동할 수 있으므로, 각 칸까지 도달하는 최단 경로의 개수를 누적하는 방식으로 해결합니다.
물웅덩이가 있는 위치는 puddle 배열에 따로 표시해두고, 해당 위치로는 경로를 더하지 않도록 처리합니다.

arr[i][j]에는 해당 위치까지 올 수 있는 경로의 개수를 저장합니다.
왼쪽에서 현재 칸으로 이동하는 경우와, 현재 칸에서 아래쪽으로 이동하는 경우를 각각 계산하며 값을 누적합니다.

소스 코드

---

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int[][] arr = new int[n + 1][m + 1];
        boolean[][] puddle = new boolean[n + 1][m + 1];

        for (int[] tmp : puddles) {
            puddle[tmp[1] - 1][tmp[0]] = true;
        }

        arr[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= m; j++) {
                if (!puddle[i][j]) {
                    arr[i][j] = (arr[i][j] + arr[i][j - 1]) % 1000000007;
                }

                if (!puddle[i + 1][j]) {
                    arr[i + 1][j] = (arr[i + 1][j] + arr[i][j]) % 1000000007;
                }
            }
        }

        return arr[n][m];
    }
}

코드 설명

---

puddle 배열은 물웅덩이 위치를 저장하는 배열입니다.
문제에서 주어지는 물웅덩이 좌표는 [x, y] 형식이므로, 세로 위치는 tmp[1], 가로 위치는 tmp[0]을 사용합니다.

arr[0][0]을 1로 두고 시작하여 첫 번째 행의 왼쪽에서 오른쪽으로 값이 전달되도록 합니다.
각 칸에서는 왼쪽에서 올 수 있는 경우를 현재 칸에 더하고, 현재 칸의 값을 아래쪽 칸으로 전달합니다.

물웅덩이인 칸은 이동할 수 없기 때문에 해당 위치에는 값을 더하지 않습니다.
마지막으로 학교 위치에 해당하는 arr[n][m] 값을 반환합니다.