LeetCode: 63번 (Unique Paths II) [JAVA]

문제 링크

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

Unique Paths II - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 주어진 2차원 배열을 한 번 돌며 장애물 표시인 1을 -1로 변경
2. 시작 위치인 [0][0]을 1로 표시
3. 2차원 배열의 0번째 행에 있는 열들과 0번째 열에 있는 행들의 요소를 돌며, 해당 위치나 이전 위치가 장애물이 아니라면 1로 표시
4. 그 외의 구역을 이중 for문을 통해 돌면서, 현 위치, 혹은 이전 왼쪽 위치, 이전 위쪽 위치가 장애물이냐 아니냐에 따라 값을 계산
5. 이차원 배열의 오른쪽 아래 값을 반환

 이 문제는 앞서 풀었던 62. Unique Paths 문제에 장애물이 추가된 버전으로, 앞서 풀었던 문제 방식에서 장애물 검증만을 추가하면 되는 문제이다. 
 우선 주어진 이차원 배열 obstacleGrid을 전체적으로 한 번 돌면서, 기존 1로 표시된 장애물 위치를 -1로 초기화해준다. 이후 시작 위치인 0행 0열을 1로 초기화 해주고, 0번째 행의 열들을 증가하는 순서대로 1을 저장, 0번째 열의 행들을 증가하는 순서대로 1을 저장한다. 다만 이 때 장애물이 있는 경우 그 너머를 1로 초기화할 수 없기 때문에, 해당 부분을 검증하는 과정을 추가한다. 이후 그 외의 요소에 대해선, 왼쪽 위부터 순차대로 이중 for문을 통해 현 위치에 대해 왼쪽 위치, 위쪽 위치의 누적값을 현 위치에 저장하면 된다. 이 때도 마찬가지로 사용할 위치 3개가 장애물인지 아닌지에 따라, 해당 값을 추가해야 하는지를 결정하면 된다. 이후 계산이 끝나고 최종 목적지인 이차원 배열의 오른쪽 아래 위치의 값을 반환하면 된다.

 

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

        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) {//시작과 끝에 장애물이 있는 경우
            return 0;
        }

        for(int r = 0;r<m;r++){
            for(int c = 0; c<n;c++){
                if(obstacleGrid[r][c]==1){//장애물 표시를 1에서 -1로 수정
                    obstacleGrid[r][c] = -1;
                }
            }
        }

        obstacleGrid[0][0] = 1;

        for (int i = 1; i < m; i++) {//0열의 행들에 대한 처리
            if (obstacleGrid[i][0] != -1 && obstacleGrid[i - 1][0] == 1) {
                obstacleGrid[i][0] = 1;
            }
        }

        for (int i = 1; i < n; i++) {//0행의 열들에 대한 처리
            if (obstacleGrid[0][i] != -1 && obstacleGrid[0][i - 1] == 1) {
                obstacleGrid[0][i] = 1;
            }
        }

        for (int r = 1; r < m; r++) {
            for (int c = 1; c < n; c++) {
                if (obstacleGrid[r][c] != -1) {//현 위치가 장애물이 없다면
                    if (obstacleGrid[r - 1][c] != -1) {//왼쪽에 장애물이 없다면
                        obstacleGrid[r][c]+=obstacleGrid[r-1][c];
                    }
                    if (obstacleGrid[r][c - 1] != -1) {//위쪽에 장애물이 없다면
                        obstacleGrid[r][c]+=obstacleGrid[r][c-1];
                    }
                }
            }
        }

        return obstacleGrid[m - 1][n - 1];//목적지 반환
    }
}

결과