(Leetcode) 62 - Unique Paths 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
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) 이다.