먼가 쉬운듯 어려운문제였다.
그림은 m=4, n=3 인 경우로
가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성하는 문제이다.
제한사항
1. 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
2. m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
3. 물에 잠긴 지역은 0개 이상 10개 이하입니다.
4. 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.
입력/출력
m: 4
n: 3
puddles:[[2, 2]]
return: 4
풀이
실수 포인트
1. 처음부터 행렬의 m,n이 거꾸로 되어 있는문제라 그냥 은근 꼬이는 부분이 생김.
2. puddles 입력부분으로 받은것을 home[][]배열에 넣을때 처리
-- 최초 집의 위치가 1,1이기 때문에 -1을 해서 넣어야함
3. 경로를 움직일때는 오른쪽으로 가는방법, 아래로 가는 방법만 있음.
-- 제일 윗줄로 오른쪽으로 이동은 [0][1], [0][1]... 한번이기에 1로 셋팅할수 있다. 그렇지만!!! 주어진 puddles가 있다면, break
-- 제일 왼쪽줄 아래로 이동도 [1][0], [2][0]... 한번이기에 1로 셋팅할 수 있다. 그렇지만!!! 이것도 똑같이 주어진 puddles가 있다면, break
이 실수 포인트를 제외하고는 최단거리를 구하기 위해서 1,1에서 부터 한칸 왼쪽, 한칸 위에 있는 이동횟수를 더한 값을 현재 값으로 넣으면서 이동하면된다.
public int solution(int m, int n, int[][] pu) {
int[][] home = new int[n][m];
// 배열의 위치에 -1을 넣는다.
for (int i = 0; i < pu.length; i++) {
int a = pu[i][0];
int b = pu[i][1];
//puddles에서 -1한값을 배열에 넣어줘야함 puddles은 1,1에서 시작함
home[b - 1][a - 1] = -1;
}
for (int i = 0; i < n; i++) {
if (home[i][0] == -1)
break; //중간에 puddles값이 있으면 중단 : 더이상 이동할 수 없음
home[i][0] = 1;
}
for (int j = 0; j < m; j++) {
if (home[0][j] == -1)
break; //중간에 puddles값이 있으면 중단 : 더이상 이동할 수 없음
home[0][j] = 1;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (home[i][j] != -1) {
//윗칸에 -1이 있으면 0 아니면 윗칸 값
int a = home[i - 1][j] == -1 ? 0 : home[i - 1][j];
//왼쪽칸에 -1이 있으면 0 아니면 왼쪽칸 값
int b = home[i][j - 1] == -1 ? 0 : home[i][j - 1];
//윗칸값 + 왼쪽칸값에 % 1000000007
home[i][j] = (a + b) % 1000000007;
}
}
}
return home[n - 1][m - 1];
}