[프로그래머스] Lv.3 등굣길 JavaScript

Janet·2023년 10월 10일
0

Algorithm

목록 보기
274/314

문제 설명

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

입출력 예

mnpuddlesreturn
43[[2, 2]]4

입출력 예 설명


문제풀이

이 문제에서 BFS가 아닌 DP를 사용해야 하는 이유는 무엇일까?

  1. 최적 부분 구조와 중복 부분 문제: 이 문제는 최적 부분 구조를 가지고 있다. 즉, 큰 문제를 작은 부분 문제로 나누어 해결할 수 있다. 또한, 같은 위치를 여러 번 방문하는 중복 부분 문제가 있다. 예를 들어, 특정 위치까지의 경로를 찾는 부분 문제를 여러 번 계산하게 된다.
  2. 메모이제이션: DP는 중복 부분 문제를 효과적으로 해결하기 위해 이전 결과를 저장하고 재사용하는 메모이제이션(Memoization)을 활용한다. 이 문제에서는 각 위치까지의 가능한 경로 수를 메모이제이션하여 중복 계산을 피하고 효율적으로 해결할 수 있다.
  3. 효율성: 이 문제는 입력의 크기가 크기 때문에 DP를 사용하여 효율적으로 해결하는 것이 좋다. BFS를 사용하면 모든 가능한 경로를 탐색해야 하므로 시간 복잡도가 더 높아질 수 있다.
  4. 필요한 정보 저장: DP를 사용하면 각 위치에서의 가능한 경로 수 뿐만 아니라, 각 위치에 도달하기 위해 필요한 최소 비용 등 다양한 정보를 저장하고 활용할 수 있다.

따라서 이 문제는 DP 알고리즘을 사용하여 최적의 경로 수를 효율적으로 구하는 것이 적합한 접근 방법이라 할 수 있다.

  1. DP 배열 초기화: dp 배열은 (n x m) 크기의 2차원 배열로, 각 원소는 해당 지점까지 갈 수 있는 경로의 수를 나타낸다. dp[i][j]는 (i+1, j+1) 위치까지 갈 수 있는 경로의 수를 의미하며, 이를 0으로 초기화한다.
  2. 물웅덩이 설정: puddles 배열에 저장된 물 웅덩이의 위치를 dp 배열에 반영한다. 물 웅덩이의 위치는 -1로 표시하여 해당 위치로는 경로가 통과되지 않도록 한다.
  3. 출발점 초기화: 출발점 (0, 0)은 경로의 시작점이므로 dp[0][0]을 1로 초기화한다.
  4. DP 배열 채우기: 이중 반복문을 사용하여 모든 지점을 탐색하며 DP 배열을 채워 나간다.
    • 현재 지점이 물웅덩이인 경우 (dp[i][j] === -1), 경로를 통과 할 수 없으므로 해당 경로는 건너뛴다.
    • 그렇지 않은 경우, (i - 1, j)에서 현재 위치인 (i, j)로 이동하려면 오른쪽으로 한 칸 이동하면 되므로, dp[i][j]를 계산할 때 (i - 1, j)의 값인 dp[i - 1][j]을 고려한다. 마찬가지로, (i, j - 1)에서 (i, j)로 이동하려면 아래쪽으로 한 칸 이동하면 되므로, dp[i][j]를 계산할 때 (i, j - 1)의 값인 dp[i][j - 1]을 고려한다.
    • 즉, 현재 위치 (i, j)에서의 가능한 경로 수가 이전 위치 (i - 1, j)(i, j - 1)에서의 가능한 경로 수를 합한 것이 된다.
    • 또한, 결과를 모듈러 연산(% 1000000007)을 통해 계산한다. 이렇게 하면 경로 수가 매우 큰 경우에도 적절하게 처리된다.
  5. 도착점 반환: 마지막으로 dp[n-1][m-1]의 값을 반환한다. 이 값은 출발점부터 도착점까지 갈 수 있는 경로의 수가 된다.

✅ 답안

function solution(m, n, puddles) {
  // dp 배열 초기화
  const dp = Array.from(Array(n), () => Array(m).fill(0));

  // 물웅덩이 좌표 -1로 저장
  puddles.forEach(([x, y]) => (dp[y - 1][x - 1] = -1));

  // 집 좌표 경로의 수가 1이므로 1로 초기화
  dp[0][0] = 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      // 시작점인 경우 해당 경로 건너뜀
	  if (i === 0 && j === 0) continue;

      // 현재 위치가 물웅덩이인 경우 해당 경로 건너뜀
      if (dp[i][j] === -1) continue;

      // 현재 위치까지 갈 수 있는 경로 수 = 현재 지점 + 위쪽 지점까지의 경로 수를 더한 값
      if (i > 0 && dp[i - 1][j] !== -1) {
        dp[i][j] = (dp[i][j] + dp[i - 1][j]) % 1000000007;
      }
			
      // 현재 위치까지 갈 수 있는 경로 수 = 현재 지점 + 왼쪽 지점까지의 경로 수를 더한 값
      if (j > 0 && dp[i][j - 1] !== -1) {
        dp[i][j] = (dp[i][j] + dp[i][j - 1]) % 1000000007;
      }
    }
  }
  // 출발점부터 도착점까지 갈 수 있는 경로의 수를 저장한 도착 지점 반환
  return dp[n - 1][m - 1];
}
profile
😸

0개의 댓글