[프로그래머스] 🏫등굣길

😀문제 설명

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

---

🤣입출력 예 설명

---

😃나의 풀이

동적 계획법 문제이다.

알고리즘 문제 풀이를 하면서 계속 느끼는건데 난 DP 문제가 좋다

상상력을 발휘해야 한다는 점과, 다른 공식없이 뇌지컬을 요구하니까(난이도가 대체적으로 괴랄하지 않아 그런 점도 크다)

function solution(m, n, puddles) {
  const MOD = 1_000_000_007;
  // n행 m열 배열 생성
  const dp = Array.from({ length: n }, () => Array(m).fill(0));

  dp[0][0] = 1;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (i === 0 && j === 0) continue;
        // 인덱스 값을 기준으로 보기에 사실상 x === j, y === i의 좌표와 같은 맥락
        // 물 웅덩이에 빠진 경우 해당 경로 값 0으로 초기화
      if (puddles.some(([x, y]) => x === j + 1 && y === i + 1)) {
        dp[i][j] = 0;
      } else {
        // x, y이동에 필요한 걸음 % MOD(문제에서 제시)
        dp[i][j] = ((i > 0 ? dp[i - 1][j] : 0) + (j > 0 ? dp[i][j - 1] : 0)) % MOD;
      }
    }
  }

    // 우측 하단까지 필요한 경로 수 반환
  return dp[n - 1][m - 1];
}