[Leetcode] 63. Unique Paths II

April Leetcode Challenge 2021에서 4월 28일에 (PST) 출시된 문제를 풀어보도록 하겠다.

문제는 아래 링크를 참고하길 바란다.

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

Unique Paths II - LeetCode

 

문제를 읽어보면 m X n 그리드가 주어지고 왼쪽 최상단에 로봇이 있다고 한다. 이 로봇은 오른쪽 또는 아래쪽으로만 이동할 수 있다고 한다. 로봇은 오른쪽 최하단의 출구로 이동하기 위해 노력한다고 한다. 여기서 그리드 내에 obstacle (장애물) 들이 주어진다면 왼쪽 최상단에서 오른쪽 최하단으로 이동하는 고유한 경로들은 총 몇 개인지를 묻는 문제이다.

그리드 내의 값은 0과 1로만 이루어져 있고 m, n은 1 이상 100 이하이다. (m은 row, n은 col을 의미한다.)

아마존이나 페북, 마소 같은 Big Tech 회사에서도 자주 출제되었다. 1~2 years엔 구글 단골 문제였다...

 

그리드가 주어지고 출발점과 도착점이 주어지는 문제는 보통 Backtracking 을 생각해서 풀면 된다.

그래서 우선 백트래킹으로 풀어보았다. 

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        /* 엣지케이스로 사이즈 체크는 인터뷰어와 상의해서 조치할 수 있도록 */
        int[][] paths = new int[obstacleGrid.length][obstacleGrid[0].length]; // 방문횟수 캐싱하기 위한 것
        for (int[] path : paths) {
            Arrays.fill(path, -1); // 0 횟수가 있으니 -1로 채움
        }
        return backtrack(obstacleGrid, 0, 0, paths); // 재귀
    }
    
    private int backtrack(int[][] obstacleGrid, int row, int col, int[][] paths) {
        if (row < 0 || col < 0 // 기본적인 바운더리 체크
         || row >= obstacleGrid.length || col >= obstacleGrid[0].length // 바운더리 체크
         || obstacleGrid[row][col] == 1) { // 현재 위치의 장애물 여부 체크
            return 0; // 이런 경우에는 갈 방법이 없으므로 0
        }
        if (row == obstacleGrid.length - 1 
         && col == obstacleGrid[0].length - 1) { // 끝에 다다랐다는 의미이므로 1회 리턴
            return 1;
        }
        if (paths[row][col] != -1) { // 방문횟수배열에 이미 값이 있으면 다시 방문할 이유가 없으므로
            return paths[row][col]; // 해당 좌표값 리턴
        }
        
        obstacleGrid[row][col] = 1; // 현재 방문상태여서 장애물 표시로 체크
        paths[row][col] = backtrack(obstacleGrid, row + 1, col, paths) // 아래로 한 칸 이동해서 탐색
                        + backtrack(obstacleGrid, row, col + 1, paths); // 오른쪽으로 한 칸 이동해서 탐색
        obstacleGrid[row][col] = 0; // 방문완료 했으니 다시 원복
        return paths[row][col];
    }
}

주의할 점은 아래 접힌글에 있는 것처럼 캐싱하지 않고 푼 경우에 테스트는 맞아도 제출 시에 시간초과 오류를 맛보실 수 있습니다.

캐시 없이 구현하더라도 어차피 물어볼겁니다.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return backtrack(obstacleGrid, 0, 0, 0);
    }
    
    private int backtrack(int[][] obstacleGrid, int row, int col, int pathCount) {
        if (row < 0 || col < 0 || row >= obstacleGrid.length || col >= obstacleGrid[0].length || obstacleGrid[row][col] == 1) {
            return pathCount;
        }
        if (row == obstacleGrid.length - 1 && col == obstacleGrid[0].length - 1) {
            return pathCount + 1;
        }
        
        obstacleGrid[row][col] = 1;
        pathCount = backtrack(obstacleGrid, row + 1, col, pathCount);
        pathCount = backtrack(obstacleGrid, row, col + 1, pathCount);
        obstacleGrid[row][col] = 0;
        return pathCount;
    }
}

 

여기서 캐시의 의미는 현재 위치까지 탐색된 고유한 길의 수를 의미하는데, 이는 재귀함수 내에서 재탐색하지 않기 위해서 사용할 것이다.

최초에 바운더리를 체크하고, 목표지점에 왔는지를 체크한 다음에 캐시 확인을 한다. 캐시 배열은 0 횟수가 가능하니 -1로 채워주는 것을 주의해야 한다. 캐시에 현재 위치의 값이 없으면 방문하고 있다는 표시를 하고 백트래킹을 재귀 호출해서 캐시값에 저장한다. 여기선 오른쪽, 아래로만 이동가능하니까 2번의 백트래킹이 더해져야하고, 모두 종료되면 방문이 종료되었다는 것을 표시하고 현재 위치의 캐시 값을 리턴한다. 

이 문제의 시간복잡도는 재귀적으로 돌아서 매우 복잡한 것처럼 보이지만 실제로 탐색하는 곳은 주어진 그리드의 전체 원소를 한번씩만 탐색한다는 것이므로 $O(m*n)$이 된다.

공간복잡도도 마찬가지로 그리드의 크기와 동일한 캐시 1개를 사용하므로 $O(m*n)$이 된다.

---

그리고 Dynamic Programming 으로도 풀 수 있다. 사실 문제를 처음 봤을때는 DP로 풀면 간단하게 풀린다는 것을 알고 있었다. 하지만 인터뷰에서 이 문제가 나와서 바로 DP로 풀면, 인터뷰어가 DP말고 다르게 풀 수 있는지를 물어볼 것이다.

한 문제를 풀때는 2개의 풀이법 정도는 숙지해둬야 하고, 어차피 시간문제로 다 하진 못하겠지만 3개까지 기억해둔다면 유리한 고지를 선점할 수 있다고 생각합니다. 풀 수 있는 방법의 가짓수가 작은데도 무리해서 찾아볼 필요는 없습니다. 특히 이 문제는 시간복잡도가 비슷한 풀이가짓수가 많은 문제이기 때문임을 알립니다.

 

그런 의미로 DP (Bottom-up) 를 통해 풀어보겠다. 코드는 아래와 같다.

DP 배열의 의미는 위 캐시에 해당하는 것과 마찬가지로 현재 위치까지 탐색된 고유한 길의 수를 담은 것이다.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[0][0] == 1) return 0; // 시작점에 장애물이 있는 경우는 외통수이므로 할 게 없음
        
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n]; // 주어진 배열과 동일한 크기의 dp 배열 선언
        dp[0][0] = 1; // 시작점에 장애물이 없으면, 갈 수 있으므로 1

        // 제일 왼쪽 열을 쭉 채움, 장애물이 있다면 그 아래로는 갈 수가 없음
        for (int row = 1; row < m; row++) { // 0은 채웠으니 1부터 시작
            if (obstacleGrid[row][0] == 1 // 그리드에 1은 장애물이 있다는 뜻이므로 0
             || dp[row - 1][0] == 0) { // 바로 위쪽 원소가 0이라는 것은 위에 장애물이 있거나, 더 위쪽에 장애물이 있다는 것을 의미
                dp[row][0] = 0;
            } else {
                dp[row][0] = 1;
            }
        }
        // 제일 상단 행을 쭉 채움, 장애물이 있다면 그 오른쪽으로는 갈 수가 없음
        for (int col = 1; col < n; col++) { // 0은 채웠으니 1부터 시작
            if (obstacleGrid[0][col] == 1 // 그리드에 1은 장애물이 있다는 뜻이므로 0 
             || dp[0][col - 1] == 0) { // 바로 왼쪽 원소가 0이라는 것은 왼쪽에 장애물이 있거나, 더 왼쪽에 장애물이 있다는 것을 의미
                dp[0][col] = 0;
            } else {
                dp[0][col] = 1;
            }
        }

        // 남은 DP 배열을 채움
        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                if (obstacleGrid[row][col] == 1) { // 그리드에 장애물이 있는 곳은 0으로 셋팅
                    dp[row][col] = 0;
                } else { // 현재 위치는 왼쪽과 위쪽 두 곳에서만 올 수 있으므로 두 개를 더해줌
                    dp[row][col] = dp[row - 1][col] + dp[row][col - 1];
                }
            }
        }
        
        return dp[m - 1][n - 1]; // 0인덱스였으니 -1 해줌
    }
}

이렇게 풀면 시간복잡도는 $O(m*n)$이 되고, 공간복잡도는 DP 배열의 크기인 $O(m*n)$이 된다. 문제는 이렇게까지 풀어도 인터뷰어는 분명 공간복잡도에 대해서 얘기를 할 것이다. 왜냐하면 주어진 그리드를 통해 in-place 형태로 풀 수 있기 때문이다.

---

in-place 형태로 푼 결과는 아래와 같다.

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        obstacleGrid[0][0] = 1; // 외통수가 아니면 갈 수 있으므로 출발지를 1로 셋팅
        for (int row = 1; row < m; row++) { // 행을 채워줌
            if (obstacleGrid[row][0] == 0 // 조건이 AND 연산이어야 함
             && obstacleGrid[row - 1][0] == 1) {
                obstacleGrid[row][0] = 1;
            } else {
                obstacleGrid[row][0] = 0;
            }
        }
        for (int col = 1; col < n; col++) { // 열을 채워줌
            if (obstacleGrid[0][col] == 0 // 조건이 AND 연산이어야 함
             && obstacleGrid[0][col -1] == 1) {
                obstacleGrid[0][col] = 1;
            } else {
                obstacleGrid[0][col] = 0;
            }
        }
        
        for (int row = 1; row < m; row++) { // 나머지도 추적하면서 채워줌
            for (int col = 1; col < n; col++) {
                if (obstacleGrid[row][col] == 1) { // 장애물이 있으면 
                    obstacleGrid[row][col] = 0; // 갈 수 없음
                } else { // 장애물이 없으면
                    obstacleGrid[row][col] = obstacleGrid[row - 1][col] // 위에서 올 수 있고
                                           + obstacleGrid[row][col - 1]; // 왼쪽에서 올 수 있음
                }
            }
        }
        
        return obstacleGrid[m - 1][n - 1]; // for-loop 돌면서 다 채워졌으니 도착지점 리턴
    }
}

DP 배열을 통한 풀이와 다른 점은 행/열을 채울때 조건이 좀 다르다. 기존에는 -1로 채워져있던 DP 배열을 주어진 그리드를 통해 새로 채우는 개념이기 때문에 그리드의 현재 위치에 장애물이 있는지를 확인하고 이전 위치 (행기준 위쪽, 열기준 왼쪽) 에 장애물이 있었는지를 확인했었다.

하지만 이 문제는 주어진 그리드에 in-place로 채울 (수정할) 예정이기 때문에 조건을 달리해줘야 한다.

조건을 보면 현재 위치의 값이 0이면서 이전 위치의 값이 1인지 확인하는 부분이 있다. 현재 위치의 값은 주어진 그리드의 기준이기 때문에 0이어야만 진행할 수 있다. (1은 장애물이다.) 그리고 이전 위치의 값이 1이라는 것은 이전 위치의 값을 다시 셋팅할때 갈 수 있는 길이었다는 뜻이다. 그러므로 주어진 (변경전) 그리드의 값이 0이면서 동시에 변경후 그리드의 값이 1이어야만 현재 행/열을 기준으로 통행할 수 있는 길이 되는 것이다.

그렇게 주어진 그리드의 각 첫번째 행과 열을 수정했으면 나머지 행렬을 수정해준다. 여기서의 조건은 방금 전 로직과 마찬가지로 주어진 (변경전) 그리드의 값에 장애물 (1) 이 있는지를 확인하고 있으면 진행할 수 없으므로 0으로 수정해준다. 장애물이 없다면 현재 위치의 값은 이전 위치가 될 수 있는 왼쪽, 위쪽에서의 경우의 수를 더한 값으로 수정해준다. 수정이 완료되었으면 마지막으로 도착지의 값을 리턴해주면 된다.

 

해당 풀이의 시간복잡도는 다른 풀이와 동일하게 $O(m*n)$이다. 근데 주어진 그리드를 수정해서 사용했기 때문에 공간복잡도가 $O(1)$이 된다.