[프로그래머스 Level.3] 등굣길 (동적계획법(Dynamic Programming)) (Java)

문제 링크

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

프로그래머스

 

 

 

 

 

코딩테스트 연습 > 동적계획법(Dynamic Programming) > 등굣길

 

 

 

문제 설명

 

 

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.

 

아래 그림은 m = 4, n = 3 인 경우입니다.

 

 

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.

 

격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

 

 

 

 

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

 

 

입출력 예

m	n	puddles	return
4	3	[[2, 2]]	4

 

 

 

 

입출력 예 설명

 

 

 

 

나의 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        int[][] dp = new int[n+1][m+1];
        
        for(int i=0; i<puddles.length; i++) {
            dp[puddles[i][1]][puddles[i][0]] = -1; 
        }
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(dp[i][j] == -1) {
                    dp[i][j] = 0; 
                } else {
                    if(i == 1 || j == 1) {
                        if(i > 1 && dp[i-1][j] == 0) continue; // 첫번째 열 중간에 웅덩이가 있으면 그 밑은 전부 0
                        if(j > 1 && dp[i][j-1] == 0) continue; // 첫번째 행 중간에 웅덩이가 있으면 오른쪽은 전부 0
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;
                    }
                }
            }
        }
        
        answer = dp[n][m];
        return answer;
    }
}

 

풀이

1. 최상단 좌측에서 최하단 우측까지 이동하는 최단 경로의 개수는 시작점에서 도착점까지 좌표를 이동하며 첫 행과 첫 열은 최단 거리로 갈 수 있는 방법이 1가지이므로 1로 채워지고 나머지는 바로 왼쪽 좌표까지의 최단 경로 수와 바로 위쪽 좌표의 최단 경로 수를 더해가면 된다. 만약 웅덩이가 있다면 웅덩이는 갈 수 없으므로 0이 된다. 또한, 웅덩이가 첫 행이나 첫 열에 있다면 첫 행 또는 첫 열의 해당 좌표부터는 0이 된다.  
   
   

   시작점 (0)	1	1	1
   1	1 + 1 = 2	웅덩이 (0)	0 + 1 = 1
   1	1 + 2 = 3	3 + 0 = 3	도착점 (3 + 1 = 4)

   
   

   시작점 (0)	1	웅덩이 (0)	0	0
   1	1 + 1 = 2	2 + 0 = 2	2 + 0 = 2	2 + 0 = 2
   웅덩이 (0)	0 + 2 = 2	2 + 2 = 4	웅덩이 (0)	0 + 2 = 2
   0	0 + 2 = 2	2 + 4 = 6	6 + 0 = 6	도착점 (6 + 2 = 8)

2. 바로 왼쪽 좌표의 값과 바로 위쪽 좌표의 값을 통해 해당 좌표의 값을 갱신해 나아가므로 dp를 이용하여 최단 경로의 수를 업데이트 해가면서 풀면 된다. 좌표 (m, n)의 값이면 배열 dp[n][m]의 값인 것에 유의하도록 한다.
3. 좌표의 크기만큼 int형 배열 dp를 생성하고 웅덩이 좌표의 자리에는 -1을 넣어 기억하도록 한다.
4. 이제 모든 좌표를 확인하면서 웅덩이 자리에는 dp가 -1로 되어있으므로 해당 좌표는 dp 값(최단 경로의 수)을 0으로 한다.
5. 그리고 첫 행과 첫 열에는 dp의 값을 1로 하고 만약 웅덩이가 있다면 첫 행과 첫 열의 해당 좌표부터는 0으로 채운다.
6. 나머지 좌표에는 dp 바로 왼쪽 좌표와 dp 바로 위의 좌표의 값을 더하여 최단 경로의 수를 업데이트 한다. 다만, 최단 경로의 수가 상당히 커질 수 있어 1,000,000,007로 나눈 나머지를 구하는 문제이므로 1,000,000,007로 나눈 나머지로 저장하도록 한다. (* 모듈로 연산 법칙을 생각하면 된다.)
7. 최종적으로 도착점의 최단 경로의 수인 도착점의 dp 값을 반환하면 된다.

 

 

* 모듈로 연산(Modulo Operation)

(A + B) % p = ((A % p) + (B % p)) % p
(A * B) % p = ((A % p) * (B % p)) % p
(A - B) % p = ((A % p) - (B % p) + p) % p