<Medium> Unique Paths II (LeetCode : C#)

https://leetcode.com/problems/unique-paths-ii/

📕 문제 설명

장애물과 빈 공간이 있는 보드에서 왼쪽 상단에 위치한 로봇이 오른쪽 하단에 도달할 수 있는 unique한 경우의 수 반환하기

• Input
  정수 배열 (mxn)
• Output
  도달 가능한 unique한 path 개수

예제

풀이

수학에서 unique한 경로 경우의 수 찾는 방식이랑 같다.

1. 먼저 첫번째 가로줄과 세로줄을 초기화 한다. (space인 경우 경우의 수로 셀 수 있어서 1로, 장애물을 만나면 그 뒤는 모두 0으로 초기화 한다.)
2. 중간 박스들의 경우 장애물이 있으면 올 수 있는 경우의 수를 0으로, 아닌 경우 왼쪽과 위쪽의 경우의 수를 합해서 본인의 경우의 수로 지정한다.
3. 모든 박스를 모두 돈 후 최종 위치의 경우의 수가 답이 된다.

public class Solution {
    public int UniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.Length;
        int n = obstacleGrid[0].Length;

        int[][] board = new int[m][];
        for (int i = 0; i< m; i++)
        {
            board[i] = new int[n];
        }

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

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

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                board[i][j] = obstacleGrid[i][j] == 1 ? 0 : board[i][j-1] + board[i-1][j];
            }
        }

        return board[m-1][n-1];
    }
}

결과