LeetCode: 62번 (Unique Paths) [JAVA]

문제 링크

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

Unique Paths - LeetCode

풀이

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

1. 주어진 m, n만큼의 2차원 배열 생성
2. 2차원 배열의 0번째 행에 있는 열들과 0번째 열에 있는 행들의 요소를 모두 1로 초기화
3. 그 외의 구역을 이중 for문을 통해 돌면서 현 위치의 누적값으로 이전 왼쪽의 값과 위의 값을 더한 값으로 저장
4. 이차원 배열의 오른쪽 아래 값을 반환

 일반적인 알고리즘 문제보다는, 수학 문제에 가깝다. 문제 자체가 최단거리로 가는 경우의 수를 구하는 문제로, 주어진 이차원 배열의 왼쪽 위에서 오른쪽 아래로 가는 경우의 수를 구하는 문제이다. 풀이의 경우 조합을 사용해서 풀 수도 있지만, 해당 문제에서는 값 누적을 반복하는 방식을 사용했다.
 우선 주어진 m, n을 바탕으로 해당 크기만큼의 이차원 배열을 생성하고, 0번째 행에 있는 열들과 0번째 열에 있는 행들의 요소를 모두 1로 초기화한다. 이는 왼쪽 위에서 시작했을 때 해당 방향으로 갈 수 있는 방법이 하나 뿐이기에 그렇다. 이제 그 외의 위치에 대해서 해당 위치로 가는 방법은 누적 연산이 필요한데, 이는 단순히 현재 위치의 왼쪽 값과 위의 값을 더하면 그만이다. 최단거리의 경우 아래에서 올라오거나 오른쪽에서 왼쪽으로 갈 일이 없기 때문에, 단순히 두 가지 값만 더하면 된다.
 그렇게 이중 for문을 통해 주어진 이차원 배열의 모든 요소의 값을 채우고 나서, 목적지인 이차원 배열 오른쪽 아래 위치의 값을 반환하면 된다.

 

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] acc = new int[m][n];

        for (int i = 0; i < m; i++) {//각 첫번째 행 1 초기화
            acc[i][0] = 1;
        }

        for (int i = 0; i < n; i++) {//각 첫번째 열 1 초기화
            acc[0][i] = 1;
        }

        for (int c = 1; c < n; c++) {
            for (int r = 1; r < m; r++) {
                acc[r][c] = acc[r - 1][c] + acc[r][c - 1];//현 위치 누적값 = 이전 행 누적값 + 이전 열 누적값
            }
        }

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

결과