[알고리즘]프로그래머스 42898번 - 등굣길

프로그래머스 42898번 - 등굣길

프로그래머스 42898번 - https://programmers.co.kr/learn/courses/30/lessons/42898

프로그래머스 42898번 - https://programmers.co.kr/learn/courses/30/lessons/42898

 

요구사항

1. 물에 잠기지 않은 지역을 통해 학교로 가려고 합니다. 단, 오른쪽과 아래쪽으로만 움직일 수 있습니다.

2. 집에서 학교까지 갈 수 있는 최단경로의 개수를 1, 000, 000, 007로 나눈 나머지를 반환하라.

 

요구사항 분석 및  풀이과정

1. 오른쪽과 아래쪽으로만 움직일 수 있다는 뜻은 특정 지역을 기준으로 해당 지역으로 들어오는 방향이 왼쪽과 위쪽밖에 없다는 것을 의미합니다.

 

2. 따라서 집에서 각 지역까지 갈 수 있는 최단경로의 개수를 dp[지역]이라고 하면 다음과 같습니다.

 

dp[지역] = dp[왼쪽 지역] + dp[위쪽 지역]

 

3. dp[지역]을 코드로 옮기기 위하여 지역을 좌표 정보로 표현하여 점화식을 정리하면 다음과 같습니다. 단, 집의 위치는 (0, 0)라고 하겠습니다.

 

집의 위치 = (0, 0)

학교의 위치 (n-1, m-1)

지역 = (x, y)

왼쪽 지역 = (x-1, y)

위쪽 지역 = (x, y-1)

 

dp[0][0] = 1

dp[우물] = -1 (도달할 수 없음)

dp[y][x] = (dp[y-1][x] + dp[y][x-1]) % 1, 000, 000, 007

 

4. dp[0][0] = 1이라는 점에서 의문을 가질 수 있습니다. 원래 0인 게 맞지만, 차후 점화식 계산에 편의를 위하여 1로 지정하였습니다.

 

왜냐하면 dp[0][1] 과 dp[1][0] 은 집에서 출발하여 바로 도착하는 최단경로만 존재하며, 값은 1이지만 dp[0][0] = 0이라면 예외가 발생하기 때문입니다.

 

점화식의 정의를 완벽하게 지키려면 dp[0][0] = 0으로 지정하되, 0행과 1열에 해당하는 지역을 따로 처리해주면 됩니다.

 

소스코드 작성

class Solution {
    
    private static final int MOD = 1_000_000_007;
    
    private static int mod(int a, int b, int mod) {
        return (a % mod + b % mod) % mod;
    }
    
    public int solution(int m, int n, int[][] puddles) {
        int [][] dp = new int[n][m];
        dp[0][0] = 1;

        for(int[] puddle : puddles) {
            int x = puddle[0] - 1;
            int y = puddle[1] - 1;
            dp[y][x] = -1;
        }

        for(int y = 0; y < n; y++) {
            for(int x = 0; x < m; x++) {

                if ((x == 0 && y == 0) || dp[y][x] == -1) {
                    continue;
                }
                       
                if (y-1 >= 0 && dp[y-1][x] != -1) {
                    dp[y][x] = mod(dp[y][x], dp[y-1][x], MOD);
                }
                
                if (x-1 >= 0 && dp[y][x-1] != -1) {
                    dp[y][x] = mod(dp[y][x], dp[y][x-1], MOD);
                }
            }
        }
        
        return dp[n-1][m-1] % MOD;
    }
}

 

결과

 

소스코드 깃허브 주소

링크