🔗 링크

https://programmers.co.kr/learn/courses/30/lessons/42898

🛣️ 문제

출발지 [1,1]에서부터 웅덩이 puddles[][]를 피해서 도착지 [m,n]로 가는

최단 거리를 1000000007로 나눈 나머지를 구해야한다.

👀 예제로 문제 파악하기

입력 : m 4, n 4, puddles [[3,2], [2,4]]

왼쪽과 오른쪽 길이가 각각 4이고, 웅덩이는 [3,2]와 [2,4]에 지정한다.

위의 값과 왼쪽 값을 더한 값을 넣어준다.

웅덩이 부분은 0으로 치고 더해준다.
(1(위쪽) + 0(웅덩이) = 1)

최종적으로 계산한 값인 7을 return한다.

😮 알고리즘 풀이 순서

1. m, n 크기의 이차원 배열을 만든다. (street[][])
2. 웅덩이 배열(puddles[][]) 크기만큼 반복문을 돌며, 해당 street 배열의 위치의 값을 -1로 초기화한다.
3. 시작점(0, 0)의 크기를 1로 초기화한다.
4. 이중 반복문을 돈다.
   • 첫 번째 반복문은 n까지(i), 두번째 반복문은 m까지(j)
5. street[i][j]의 값이 -1이라면(웅덩이) 값을 0으로 바꿔주고 (나중에 계산을 위해) 4번으로 돌아간다.
6. i의 값이 0이 아니라면 (맨 위가 아니라면) 위쪽 값을 street[i][j]에 더해준다.
7. j의 값이 0이 아니라면 (맨 왼쪽이 아니라면) 왼쪽 값을 street[i][j]에 더해준다.
8. 4번으로 돌아간다.
9. street[m - 1][n - 1]을 리턴한다.
   • m과 n은 크기를 의미하기 때문에 위치는 -1을 해주어야한다.
     
     

👨‍💻 코드

public class Solution {
  public int solution(int m, int n, int[][] puddles) {
    int[][] street = new int[n][m];

    // 웅덩이는 -1
    for (int[] puddle : puddles)
      street[puddle[1] - 1][puddle[0] - 1] = -1;

    street[0][0] = 1;

    for (int i = 0; i < n; i++) { // 시작점은 1로 저장
      for (int j = 0; j < m; j++) {

        if(street[i][j] == -1) { // 웅덩이면 0으로 바꾸고 continue
          street[i][j] = 0;
          continue;
        }

        if(i != 0)
          street[i][j] += street[i - 1][j] % 1000000007; // 숫자가 이 값을 초과할 수 있기 때문에 계산 과정에서 나머지 구하기

        if(j != 0)
          street[i][j] += street[i][j - 1] % 1000000007; // 왼쪽
      }
    }

    return street[n - 1][m - 1] % 1000000007;
  }

  @Test
  public void 정답(){
    Assert.assertEquals(4, solution(4, 3, new int[][]{{2,2}}));
    Assert.assertEquals(7, solution(4, 4, new int[][]{{3,2}, {2,4}}));
    Assert.assertEquals(7, solution(5, 3, new int[][]{{4,2}}));
    Assert.assertEquals(0, solution(2, 2, new int[][]{{2,1}, {1, 2}}));
    Assert.assertEquals(0, solution(3, 1, new int[][]{{2,1}}));

  }
}