1. 문제 설명
- m * n 크기의 격자 모양
- 집의 좌표 (1,1), 학교의 좌표 (m,n)
- int[][] puddles 좌표가 주어짐
- 오른쪽, 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1,000,000,007로 나눈 나머지를 return
제한 사항
- 1 <= n, m <= 100
- puddles는 0개 이상 10개 이하
- 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않음
2. 스크래치
문제 유형 파악: 동적 계획법(DP)
-
최적 부분 구조를 가짐
큰 문제의 해답이 작은 문제의 해답들로 구성되는 경우!
집 ~ 목표 지점까지의 최단 경로의 경우의 수는 그 이전 지점들로 오는 경우의 수들의 합으로 결정됨
문제의 제약 조건: 오른쪽 또는 아래쪽으로만 이동 가능
=> 해당 칸으로 이동하는 경우의 수 = 왼쪽에서 오는 경우 + 위쪽에서 오는 경우 -
DFS 탐색으로 푸는 경우
모든 경로를 단순 재귀 호출 (DFS)로 탐색한다면, 여러 경로를 탐색하는 과정에서 동일한 중간지점까지 도달하는 경우의 수를 반복해서 계산하게 됨
DP를 사용할 경우 한 번 계산된 결과를 메모이제이션해두고, 필요할 때마다 저장된 값을 재활용하여 계산 속도를 높임.
3. 풀이
[로직] 문제 쪼개기
1) DP 배열 정의 & 초기화
// 1. dp 배열 선언
int[][] dp = new int[n][m];
// 2. 물 웅덩이에 -1 표시 (0-based index)
for(int[] puddle: puddles){
int x = puddle[0]-1;
int y= puddle[1]-1;
dp[y][x] =-1;
}
// 3. 시작위치 표시: 집(0,0)에 1 표시
if(dp[0][0]!=-1){
dp[0][0]=1;
}else{
return 0;
}- dp 2차원 배열: 1-based index -> 0-based index
- dp 배열 선언 시 사이징 (열, 행) => (행, 열)
문제에서 m : 가로 길이 => 열, n : 세로 길이 => 행
학교의 (행,열)위치 좌표가 (3,4)이지만 (4,3)으로 표기됨
이것을 다시 (행, 열)로 바꾸어서 문제 풀기
2) DP 테이블 채우기
for(int i=0; i< n; i++){
for(int j=0; j<m; j++){
int leftPaths=0;
int topPaths=0;
// 0) 시작점 채워져 있음 -> pass
if(i==0 && j==0) continue;
// 1) 물 웅덩이라면
if(dp[i][j]==-1){
dp[i][j]=0; // 경로 개수 = 0
continue; // 다음 칸으로
}
// 3) + 위쪽 칸 경로 개수
if(i>0){
topPaths = dp[i-1][j];
}
// 4) + 왼쪽 칸 경로 개수
if(j>0){
leftPaths=dp[i][j-1];
}
// 5) !! 합산 & 모듈러 연산
dp[i][j] = (topPaths + leftPaths) % mod;
}
}- 2차원 배열을 2중 for문으로 순회하면서 탐색 좌표가 물웅덩이이거나 시작점이면 건너뜀 (continue)
- 위쪽 경로의 경우의 수를 구할 때 경계 확인: i>0
(i=0 위의 행이 없기 때문) - 왼쪽 경로의 경우의 수를 구할 때 경계 확인: j>0
(j=0 왼쪽의 행이 없기 때문)
3) 출력
answer = dp[n-1][m-1];
return answer;4. 코드
class Solution {
public int solution(int m, int n, int[][] puddles) {
final int mod = 1000000007;
int answer = 0;
// !!
// m : 가로 길이 => 열
// n : 세로 길이 => 행
// 학교의 위치: (m,n)-> (4,3) => (3,4)
// 1. dp 배열 선언
int[][] dp = new int[n][m];
// 2. 물 웅덩이에 -1 표시 (0-based index)
for(int[] puddle: puddles){
int x = puddle[0]-1;
int y= puddle[1]-1;
dp[y][x] =-1;
}
// 3. 시작위치 표시: 집(0,0)에 1 표시
if(dp[0][0]!=-1){
dp[0][0]=1;
}else{
return 0;
}
// 4. dp 테이블 채우기
for(int i=0; i< n; i++){
for(int j=0; j<m; j++){
int leftPaths=0;
int topPaths=0;
// 0) 시작점 채워져 있음 -> pass
if(i==0 && j==0) continue;
// 1) 물 웅덩이라면
if(dp[i][j]==-1){
dp[i][j]=0; // 경로 개수 = 0
continue; // 다음 칸으로
}
// 3) + 위쪽 칸 경로 개수
if(i>0){
topPaths = dp[i-1][j];
}
// 4) + 왼쪽 칸 경로 개수
if(j>0){
leftPaths=dp[i][j-1];
}
// 5) !! 합산 & 모듈러 연산
dp[i][j] = (topPaths + leftPaths) % mod;
}
}
answer = dp[n-1][m-1];
return answer;
}
}5. De-fault
fault-1. 2차원 배열의 인덱싱
- 문제
문제에서 (m,n)으로 주어졌을 때 바로 dp[m][n]으로 배열을 생성하면 인덱스가 꼬임 - 해결
문제에서 (n,m) & 1-based index
=> (m, n) & 0-based index로 바꾸기
fault-2. 자료형과 오버 플로우
- 문제
경로의 개수가 int 범위를 쉽게 초과할 수 있음. - 해결
DP 배열을 long 타입으로 선언하고, 덧셈 연산 후 반드시 % 1000000007 모듈러 연산을 적용하는 방식을 고려.
fault-3. 경계 및 물웅덩이 처리
- 문제
맨 위 줄(i=0)이나 맨 왼쪽 줄(j=0)에서
DP[i-1][j]나 DP[i][j-1]를 참조하면ArrayIndexOutOfBoundsException발생. - 해결
if (i > 0) 및 if (j > 0) 조건문을 사용하여 경계 밖 참조를 막음.
물웅덩이는 미리 0으로 설정하여, 덧셈에 포함되더라도 경로 개수 합산에 오류를 일으키지 않도록 함.
시간 복잡도: O(N*M)
- DP 배열을 순회하는 2중 for문 (
O(N*M))
N,M <= 100 - 각 칸의서의 연산 (
O(1))
이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요. 알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂
