728x90
코드 힌트
- 웅덩이 처리:
- 웅덩이(puddles)로 지정된 셀은 경로 계산에서 제외됩니다.
- 이 셀들은 -1로 표시하여, 이후 경로 계산에서 무시하도록 처리합니다.
- 초기화:
- 첫 번째 행과 첫 번째 열의 값을 초기화합니다.
- 만약 웅덩이로 인해 막혀있는 경우 해당 경로는 막히며, 그렇지 않은 경우 1로 설정합니다.
- 이는 초기 경로 설정을 위한 작업입니다.
- 동적 프로그래밍:
- 나머지 셀들은 동적 프로그래밍을 이용하여 계산합니다.
- 각 셀의 경로 수는 왼쪽과 위쪽에서 올 수 있는 경로의 수를 합산하여 계산합니다.
- 이 과정에서 현재 셀이 웅덩이인지 확인하고, 웅덩이가 아닌 경우에만 경로 수를 누적합니다.
- 결과 반환:
- 최종적으로 도착 지점 (m-1, n-1)의 셀에 저장된 경로 수를 반환합니다.
- 결과는 매우 큰 수를 다룰 수 있으므로, 1,000,000,007로 나머지 연산을 수행하여 반환합니다.
정답은 더보기 클릭
더보기
class Solution {
public int solution(int m, int n, int[][] puddles) {
int[][] map = new int[m][n];
// 웅덩이 초기화: 웅덩이는 -1로 표시
for (int[] puddle : puddles) {
map[puddle[0]-1][puddle[1]-1] = -1;
}
// 첫 번째 열 초기화: 웅덩이로 막혀 있지 않은 경우만 1로 설정
for (int i = 1; i < m; i++) {
if (map[i][0] != -1 && map[i-1][0] != -1) {
map[i][0] = 1;
} else {
map[i][0] = -1;
}
}
// 첫 번째 행 초기화: 웅덩이로 막혀 있지 않은 경우만 1로 설정
for (int j = 1; j < n; j++) {
if (map[0][j] != -1 && map[0][j-1] != -1) {
map[0][j] = 1;
} else {
map[0][j] = -1;
}
}
// 나머지 셀 계산: 왼쪽 및 위쪽 셀의 경로 수를 합산
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
// 현재 셀이 웅덩이인 경우 무시
if (map[i][j] == -1) continue;
// 왼쪽 셀에서 오는 경로 추가 (왼쪽 셀이 웅덩이가 아닌 경우)
if (j-1 >= 0 && map[i][j-1] != -1) {
map[i][j] += map[i][j-1];
}
// 위쪽 셀에서 오는 경로 추가 (위쪽 셀이 웅덩이가 아닌 경우)
if (i-1 >= 0 && map[i-1][j] != -1) {
map[i][j] += map[i-1][j];
}
// 경로 수는 큰 수를 피하기 위해 1,000,000,007로 나머지 연산 수행
map[i][j] %= 1000000007;
}
}
// 도착 지점의 경로 수 반환
return map[m-1][n-1];
}
}
728x90
'프로그래머스(Java) > Level 3' 카테고리의 다른 글
[프로그래머스] 숫자 게임 (0) | 2024.09.03 |
---|---|
[프로그래머스] 베스트앨범 (1) | 2024.09.02 |
[프로그래머스] N으로 표현 (0) | 2024.08.21 |
[프로그래머스] 야근 지수 (0) | 2024.08.19 |
[프로그래머스] 단어 변환 (0) | 2024.08.02 |