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

 

 

---

문제 출처 

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

프로그래머스

 

문제 풀이

- 동적 프로그래밍 (Dynamic Programming) 문제 

- 시간 복잡도 : O(NM) 

- 격자형 그래프가 주어졌을 때 (1,1) -> (n, m)으로 이동하는 경우의 수를 구하는 문제

- 이때 이동 방향은 오른쪽과 아래쪽으로만 이동가능하다

 

① dp 배열을 정의하고, 물 웅덩이 영역을 -1로 표시한다 (이때 puddles가 m,n으로 주어져서 주의 필요)

int row = n;
int col = m;
int[][] dp = new int[row + 1][col + 1];

for(int[] p : puddles) {
    dp[p[1]][p[0]] = -1; // 물 웅덩이 표시
}

 

② (1,1)에서 오른쪽과 아래 영역을 초기화한다. 

이때 물 웅덩이(-1) 만날 경우 이동 방향 제한으로 못 가므로 break 종료한다

for(int i = 1; i <= col; i++) {
    if(dp[1][i] == -1) break;

    dp[1][i] = 1;
}

for(int i = 1; i <= row; i++) {
    if(dp[i][1] == -1) break;

    dp[i][1] = 1;
}

 

 

③ 2중 반복문을 돌면서 값을 갱신한다  

 

예. (2,3)의 경우 왼쪽(2,2)에서 오는 경우와 위(1,3)에서 오는 경우에서 왼쪽은 물웅덩이므로 합산하지 x 

그리고 합산시 mod(1억 7)로 나눠주도록 한다

 

int mod = 1_000_000_007;
for(int i = 2; i <= row; i++) {
    for(int j = 2; j <= col; j++) {
        if(dp[i][j] == -1) continue; // 물 웅덩이인 경우

        if(dp[i - 1][j] != -1) { // 위가 물웅덩이가 아닌 경우
            dp[i][j] += dp[i - 1][j];
            dp[i][j] %= mod;
        }

        if(dp[i][j - 1] != -1) { // 왼쪽이 물웅덩이가 아닌 경우
            dp[i][j] += dp[i][j - 1];
            dp[i][j] %= mod;
        }
    }
}

 

 

④ 최종적으로 dp[n][m] 결과를 반환한다

 

전체 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int mod = 1_000_000_007;
        
        int row = n;
        int col = m;
        int[][] dp = new int[row + 1][col + 1];
        
        for(int[] p : puddles) {
            dp[p[1]][p[0]] = -1; // 물 웅덩이 표시, m, n 위치 주의 *
        }
        
        for(int i = 1; i <= col; i++) {
            if(dp[1][i] == -1) break;
            
            dp[1][i] = 1;
        }
        
        for(int i = 1; i <= row; i++) {
            if(dp[i][1] == -1) break;
            
            dp[i][1] = 1;
        }
        
        for(int i = 2; i <= row; i++) {
            for(int j = 2; j <= col; j++) {
                if(dp[i][j] == -1) continue;
                
                if(dp[i - 1][j] != -1) {
                    dp[i][j] += dp[i - 1][j];
                    dp[i][j] %= mod;
                }
                
                if(dp[i][j - 1] != -1) {
                    dp[i][j] += dp[i][j - 1];
                    dp[i][j] %= mod;
                }
            }
        }
    
        
        return dp[row][col];
    }
}