🎯문제
계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 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 |
입출력 예 설명
✏️풀이
코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] dp = new int[n][m];
// 물에 잠긴 지역은 -1로 값을 채워줌
for(int i = 0; i < puddles.length; i++) {
dp[puddles[i][1] - 1][puddles[i][0] - 1] = -1;
}
// 초깃값 설정
dp[0][0] = 1;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// 물이 있는 지역일 경우
if(dp[i][j] == -1) {
// 해당 지역의 값을 0으로 바꾼 뒤 continue
dp[i][j] = 0;
continue;
}
// i가 0이 아닐 때
if(i != 0) {
dp[i][j] += dp[i-1][j] % 1000000007;
}
// j가 0이 아닐 때
if(j != 0) {
dp[i][j] += dp[i][j-1] % 1000000007;
}
}
}
// 저장된 값을 MOD로 나눠서 반환
return dp[n-1][m-1] % 1000000007;
}
}설명
dp의 방식을 사용하여 진행하였다.
dp 배열을 생성해준다. 이때 x좌표는 n이고 y좌표는 m이므로 둘의 순서가 바뀌지 않게 유의한다.
물에 잠긴 지역의 dp 배열의 값은 -1로 채워준다. 이때 마찬가지로 puddles[i][1]이 x좌표, puddles[i][0]이 y좌표가 된다.
초깃값을 1로 설정해준 뒤 반복문을 진행한다.
i = 0부터 n-1까지, j = 0부터 m-1까지 진행을 하며 물이 있는 지역일 경우 해당 지역의 값을 0으로 바꾼 뒤에 continue를 진행한다.
i != 0일 경우 i-1이라는 값이 존재하므로 [i-1][j] % 1,000,000,007을 계산하여 값을 더해준다.
j != 0일 경우 j-1이라는 값이 존재하므로 [i][j-1] % 1,000,000,007을 계산하여 값을 더해준다.
이렇게 위의 모든 반복이 끝난 뒤에 저장된 도착지점의 값에 1,000,000,007로 나머지 연산을 진행하여 나온 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
dp의 방식을 사용하여 푸는 문제였다. 문제를 푸는 방식 자체는 쉽게 생각할 수 있었지만 x, y좌표를 헷갈려서 어디가 문제인지 코드를 계속 읽어봤었다.. 문제를 풀면서 푸는 실력도 중요하지만 문제의 조건들과 코드를 이해하는 것이 기본적으로 받쳐줘야 더욱 쉽게 풀 수 있음을 뼈져리게 느끼고 있다.. 아직은 미숙하니 조금 더 열심히 노력해야지..!
링크
