문제 설명
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 |
입출력 예 설명
문제풀이
이 문제에서 BFS가 아닌 DP를 사용해야 하는 이유는 무엇일까?
- 최적 부분 구조와 중복 부분 문제: 이 문제는 최적 부분 구조를 가지고 있다. 즉, 큰 문제를 작은 부분 문제로 나누어 해결할 수 있다. 또한, 같은 위치를 여러 번 방문하는 중복 부분 문제가 있다. 예를 들어, 특정 위치까지의 경로를 찾는 부분 문제를 여러 번 계산하게 된다.
- 메모이제이션: DP는 중복 부분 문제를 효과적으로 해결하기 위해 이전 결과를 저장하고 재사용하는 메모이제이션(Memoization)을 활용한다. 이 문제에서는 각 위치까지의 가능한 경로 수를 메모이제이션하여 중복 계산을 피하고 효율적으로 해결할 수 있다.
- 효율성: 이 문제는 입력의 크기가 크기 때문에 DP를 사용하여 효율적으로 해결하는 것이 좋다. BFS를 사용하면 모든 가능한 경로를 탐색해야 하므로 시간 복잡도가 더 높아질 수 있다.
- 필요한 정보 저장: DP를 사용하면 각 위치에서의 가능한 경로 수 뿐만 아니라, 각 위치에 도달하기 위해 필요한 최소 비용 등 다양한 정보를 저장하고 활용할 수 있다.
따라서 이 문제는 DP 알고리즘을 사용하여 최적의 경로 수를 효율적으로 구하는 것이 적합한 접근 방법이라 할 수 있다.
- DP 배열 초기화:
dp배열은 (n x m) 크기의 2차원 배열로, 각 원소는 해당 지점까지 갈 수 있는 경로의 수를 나타낸다.dp[i][j]는 (i+1, j+1) 위치까지 갈 수 있는 경로의 수를 의미하며, 이를 0으로 초기화한다. - 물웅덩이 설정:
puddles배열에 저장된 물 웅덩이의 위치를dp배열에 반영한다. 물 웅덩이의 위치는 -1로 표시하여 해당 위치로는 경로가 통과되지 않도록 한다. - 출발점 초기화: 출발점 (0, 0)은 경로의 시작점이므로
dp[0][0]을 1로 초기화한다. - 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)을 통해 계산한다. 이렇게 하면 경로 수가 매우 큰 경우에도 적절하게 처리된다.
- 현재 지점이 물웅덩이인 경우 (
- 도착점 반환: 마지막으로
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];
}