[PS] 99클럽 코테 스터디 41일차 TIL (Unique Paths2)

문제

문제 링크

설명

로봇이 격자 왼쪽 상단부터 오른쪽 하단 끝까지 이동하는 경우의 수를 찾는 문제. 이전 문제와 구현 방식은 같다. 단, 중간에 장애물이 있는 경우 그쪽으로는 갈 수 없다는 조건이 있다.

풀이

1. dp 배열 정의 : (i,j) 영역에 도달하는 경로의 수
   • (i,0) / (0,j) 줄은 경우의 수가 하나뿐이므로 미리 채워 놓는다.
   • 장애물이 있는 경우 0, 아닌 경우 1로 세팅한다.
     • 장애물 이후의 경로는 못지나가므로 break
2. 점화식 도출 : 문제에서 로봇은 오른쪽 또는 아래 로 밖에 움직이지 못한다고 했으므로 (i, j) 영역에 도달하는 경우의 수는 왼쪽에서 오는 경우의 수 + 위에서 오는 경우의 수로 나타낼 수 있다.
   • dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
   • 장애물이 있는 경우(obstacleGrid[i][j] == 1) 그 경로엔 도달할 수 없으므로 0으로 세팅

class Solution {
  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    int[][] dp = new int[m][n];

    for (int i = 0; i < m; i++) {
      if (obstacleGrid[i][0] == 1) {
        dp[i][0] = 0;
        break;
      } else {
        dp[i][0] = 1;
      }
    }

    for (int i = 0; i < n; i++) {
      if (obstacleGrid[0][i] == 1) {
        dp[0][i] = 0;
        break;
      } else {
        dp[0][i] = 1;
      }
    }

    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        if (obstacleGrid[i][j] == 1) {
          dp[i][j] = 0;
        } else {
          dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
      }
    }
    return dp[m - 1][n - 1];
  }
}