[DP] 등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=javascript 

프로그래머스

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

 

로직

점화식

dp[i][j] = dp[i-1][j] + dp[i][j-1];
현재위치 까지의 경로 갯수 = 위에 까지의 경로 갯수 + 왼쪽까지의 경로갯수

 

1. dp 이차배열을 선언하고 undefined로 채운다

2. dp에서 먼저 시작위치인 dp[0][0] = 경로갯수 1로,  puddles을 0으로 변경해준다.

3. 이중for로 dp를 돌면서 위의 점화식으로 dp를 채운다. (현재 = 상위 + 좌측)

3-1. 이때  상위나 좌측이 배열을 벗어나거나 웅덩이면 0으로 계산한다.

4. 마지막 항 마지막 열의 경로최대 갯수를 리턴한다.

 

주의

• m,n는 각각 열, 항으로 반대다
• puddles도 마찬가지로 반대다
• 오른쪽, 왼쪽으로만 이동가능하다
• 나머지 값을 리턴한다 1000000007 모듈러 계산법
• 모든 첫항이나 모든 첫열이 무조건 1인건 아니다 아래 예 (따라서 첫항과 첫열도 점화식대로 구해야한다)

 

 

모듈러 계산법

문제 풀이에서 1000000007, 1000000009으로 나누는 이유가 뭐지? (feat.모듈로 연산)

답을 출력할 때 100000007로 나눈 나머지를 리턴하는 경우가 있다.

이는 답을 다 구해놓고 출력 직전에 나머지 연산을 하기에는 값이 너무 커지는 경우 오류가 나기 떄문에

답을 계산하는 과정에서 중간중간 나머지 연산을 통해 값을 줄여줘야 한다

 

int형식은 32비트로 표현되고 표현할 수 있는 범위는 -2147483648 ~ 2147483647 이다.
long형식은 64비트로 표현되고 표현할 수 있는 범위는 -9.22337204e18 ~ 9.22337204e18이다.

이게 가끔 문제에서 계산하다보면 저 이상의 숫자가 나오면 overflow가 나와 문제가 생긴다.

이때 아래 법칙에 따라 값을 줄여줄 수 있다.

 

연산자 분배법칙

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

예를 들어서

(13+5)%8 = ((13%8) + (5%8)) % 8 -> 2

 

근데 왜 1000000007, 1000000009로 나누지...?

아까 위에서 본 int는 -2147483648 ~ 2147483647 의 범위를 가진다.
근데 이거를 또 맨날 나머지 연산을 하면 int의 표현을 최대한 활용하는게 힘들 것이다.
그래서 최대한 int의 max에 가깝도록 쓰는데, 그 중에서도 절반에 해당하는 소수값인 1000000007 혹은 1000000009를 사용하는 것이다. (진짜 max에 가까우면 연산 도중에 overflow발생 가능!!) 

소수는 두가지 장점을 갖는데

• 연산의 정확도가 높다.
• 해당 모듈러 곱셈의 역을 구하는 것이 쉽다.

결론

알고리즘 풀이에서 1000000007, 1000000009등으로 나누는 이유는

• 연산자 분배법칙에 의해 mod 결과 같은 값을 도출해낸다.
• int의 max의 절반에 해당하기 때문에 stackoverflow 방지 가능
  • int의 범위를 최대한 활용하기 위해 max의 절반에 최대한 가까운 숫자들 사용
• 두 값은 소수이다.
  • 연산의 결과가 더 정확하다.
  • 역산을 구하기 쉬움

레퍼런스

 

따라서 큰 숫자가 나올 수 있는 부분에 mod계산을 해주면 오류를 방지할 수 있다!

 

전체코드

function solution(m, n, puddles) {
    var answer = 0;
    const dp = Array.from({length: n}, () => Array.from({length: m}, () => undefined));
    dp[0][0] = 1;
    
    // 물웅덩이 // 좌표가 반대!
    for (const [pCol, pRow] of puddles) {
        dp[pRow-1][pCol-1] = 0;
    }
    
    // n, m반대
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (i === 0 && j === 0) {
                continue;
            }
            // 웅덩이는 패스
            if (dp[i][j] !== 0) {
                let top = 0;
                let left = 0;
                
                // 이차배열 범위 안 이고 && 물웅덩이가 아니면 dp의 값을 가져온다
                if (i-1 >= 0 && dp[i-1][j] !== 0) {
                    top = dp[i-1][j];
                }
                if (j-1 >= 0 && dp[i][j-1] !== 0) {
                    left = dp[i][j-1];
                }
                dp[i][j] = (top + left) % 1000000007; // 현재 = 상 + 좌
            }
        }
    }
    return dp[n-1][m-1] % 1000000007;
}