[Programmers] 등굣길

난이도 : Level 3

문제링크

• 집에서 학교까지 갈 수 있는 최단 경로의 개수의 1,000,000,007로 나눈 나머지를 리턴하라
• 물웅덩이가 있는 길은 지나갈 수 없음
• 집 좌표 : (0,0)
• 학교 좌표 : (m-1, n-1)

 

해설

• 동적계획법을 사용하여 도착지별 최단 경로수를 구해나간다.
  • 도착지의 최단 경로 수는 도착지로부터 위, 왼쪽 도착지의 경로의 합입니다.
  • 물웅덩이를 만나게 될 경우, 해당 경로의 최단경로 수는 0이 됩니다.
  • 첫번째 열 혹은 첫번째 행일경우, 직전에 방문한 도착지의 최단경로만 더해줍니다.

public int solution(int m, int n, int[][] puddles) {
    int[][] dp = new int[n+1][m+1];
    for (int[] puddle : puddles) {
        dp[puddle[1]][puddle[0]] = -1;
    }

    dp[1][1] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (dp[i][j] == -1) { // 물에 잠긴 구역
                dp[i][j] = 0;
                continue;
            }
            if (i != 1) {
                dp[i][j] += dp[i-1][j] % 1000000007;
            }
            if (j != 1) {
                dp[i][j] += dp[i][j-1] % 1000000007;
            }
        }
    }

    return dp[n][m] % 1000000007;
}