박종훈 알고리즘 블로그

(Leetcode) 62 - Unique Paths 풀이

기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.

https://neetcode.io/practice


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

어렸을 때 풀었던 확률 문제가 떠오르는 문제이다. 그 때 했던 풀이 그대로 코드로 옮겨보았다.

내가 작성한 풀이

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

        Deque<Coordinate> deque = new ArrayDeque<>();
        deque.addLast(new Coordinate(1, 0));
        deque.addLast(new Coordinate(0, 1));
        while (!deque.isEmpty()) {
            Coordinate coordinate = deque.removeFirst();
            if (coordinate.x >= m || coordinate.y >= n || matrix[coordinate.x][coordinate.y] != 0) {
                continue;
            }

            int top = coordinate.y > 0 ? matrix[coordinate.x][coordinate.y - 1] : 0;
            int left = coordinate.x > 0 ? matrix[coordinate.x - 1][coordinate.y] : 0;
            matrix[coordinate.x][coordinate.y] = top + left;

            deque.addLast(new Coordinate(coordinate.x + 1, coordinate.y));
            deque.addLast(new Coordinate(coordinate.x, coordinate.y + 1));
        }

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

class Coordinate {
    int x;
    int y;

    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

TC, SC

시간 복잡도는 O(m * n) 공간 복잡도는 O(m * n) 이다.