99클럽 코테 스터디 41일차 TIL , Unique Paths II

문제

풀이

어제의 문제의 업그레이드 형이다.

그리드가 주어지는데 그리드 어디에든 장애물이 있을 수 있다.

장애물에는 들리지 않고 도착점인 m-1, n-1까지 가는 최소 경로의 개수를 구하면 된다.

 

제출 1 - 정답

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

        //시작점, 도착점이 장애물이면 불가능
        if(obstacleGrid[m-1][n-1] == 1 || obstacleGrid[0][0] == 1) return 0;
		
        //0을 포함하고 있으면 1로 채우지만 도중에 장애물이 있다면 장애물 포함 그 뒤로 -1로 채움
        int x = 1;
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0] == 1) x = -1;
            obstacleGrid[i][0] = x;
        }
        x = 1;
        for(int i=1;i<n;i++){
            if(obstacleGrid[0][i] == 1) x = -1;
            obstacleGrid[0][i] = x;
        }

		
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
            	//전체를 돌면서 장애물을 만나면 -1로 바꾸고 넘어감
                if(obstacleGrid[i][j] == 1){
                    obstacleGrid[i][j] = -1;
                    continue;
                }
                //위, 왼이 장애물이면 0으로 하고 아니면 그대로 가져옴
                int up = obstacleGrid[i-1][j] == -1 ? 0 : obstacleGrid[i-1][j];
                int left = obstacleGrid[i][j-1] == -1 ? 0 : obstacleGrid[i][j-1];

				//위, 왼을 더해줌
                obstacleGrid[i][j] = up + left;
            }
        }
		
        //도착점 출력
        return obstacleGrid[m-1][n-1];
    }
}

 

어제와 똑같은 방식으로 풀면 되지만 조금 추가를 해야한다.

장애물이 생겼더라도 최단 거리를 계산하는 방법은 똑같다.

장애물이 있을 경우에는 더해주지 않으면 된다.

방법은 알았지만 예외경우를 생각하지 못해서 시간이 꽤 걸렸다.

TIL

• DP