프로그래머스 [Lv. 3] 등굣길 {언어 : JavaScript}

문제 링크

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

프로그래머스

정답 코드

function solution(m, n, puddles) {
    // DP 배열 초기화
    let dp = Array(n + 1).fill(0).map(() => Array(m + 1).fill(0));

    // 시작 지점 설정
    dp[1][1] = 1;

    // 물웅덩이 설정
    puddles.forEach(([c, r]) => {
        dp[r][c] = -1;
    });

    // DP를 이용한 경로의 개수 계산
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            // 시작 지점 또는 물웅덩이인 경우 스킵
            if ((i === 1 && j === 1) || dp[i][j] === -1) continue;

            if (dp[i - 1][j] > 0) dp[i][j] += dp[i - 1][j] % 1000000007;
            if (dp[i][j - 1] > 0) dp[i][j] += dp[i][j - 1] % 1000000007;
        }
    }

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

풀이 방법

1. dp 배열을 만든다.
2. 어차피 위에서 아래로 내려가면서 할 것이기 때문에 반복문 2개를 돌린다.
   1. 시간 복잡도는 O(n^2)이지만 n이 100이하 자연수이므로 가능하다.
3. 계산 중간 중간에 1000000007로 나머지를 구해주면서 더한다.

느낀점

• 처음에 bfs로 풀었다가 시간초과가 났다.
• 단순하게 반복문으로도 가능하다는 것을 깨달았다.