계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.
m | n | puddles | return |
---|---|---|---|
4 | 3 | [[2, 2]] | 4 |
이 문제에서 BFS가 아닌 DP를 사용해야 하는 이유는 무엇일까?
따라서 이 문제는 DP 알고리즘을 사용하여 최적의 경로 수를 효율적으로 구하는 것이 적합한 접근 방법이라 할 수 있다.
dp
배열은 (n x m) 크기의 2차원 배열로, 각 원소는 해당 지점까지 갈 수 있는 경로의 수를 나타낸다. dp[i][j]
는 (i+1, j+1) 위치까지 갈 수 있는 경로의 수를 의미하며, 이를 0으로 초기화한다.puddles
배열에 저장된 물 웅덩이의 위치를 dp
배열에 반영한다. 물 웅덩이의 위치는 -1로 표시하여 해당 위치로는 경로가 통과되지 않도록 한다.dp[0][0]
을 1로 초기화한다.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];
}