.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Example 1:
Input: m = 3, n = 7
Output: 28
Plain Text
복사
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
Plain Text
복사
Example 3:
Input: m = 7, n = 3
Output: 28
Plain Text
복사
Example 4:
Input: m = 3, n = 3
Output: 6
Plain Text
복사
Constraints:
•
1 <= m, n <= 100
•
It's guaranteed that the answer will be less than or equal to 2 * .
My solution
미로찾기 하듯이 풀면 될거라고 생각했는데 원래 미로찾기는 0과 1로 구별되어 있는 배열이 주어지는데 이 경우는 직접 0으로 채워진 배열을 가지고 좌측상단에서 우측하단으로 최단거리로 이동하게 해야했다.
그래서 min을 잡아서 레벨로 이동한 개수를 센다음 이 min보다 같거나 작을 때만 answer를 증가시키게 했다. 이렇게 하면 문제는 최단 거리가 몇인지를 모르는 상태에서 answer를 늘릴 수 없었다.
⇒ 오른쪽, 아래로만 이동하게 제한하면 경로는 항상 최단경로이므로 이 경로들의 개수를 구하면 그게 답이 된다.
const uniquePaths = function (m, n) {
let answer = 0;
const arr = [...Array(m)].map(() => Array(n).fill(0));
let min = 0;
const dx = [-1, 0, 1, 0];
const dy = [0, -1, 0, 1];
function DFS(r, c, L) {
if (min <= L && r === m - 1 && c === n - 1) {
min = L;
answer++;
} else {
for (let i = 0; i < 4; i++) {
const nr = r + dx[i];
const nc = c + dy[i];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && arr[nr][nc] === 0) {
arr[nr][nc] = 1;
DFS(nr, nc, L + 1);
arr[nr][nc] = 0;
}
}
}
}
arr[0][0] = 1;
DFS(0, 0, 0);
return answer;
};
JavaScript
복사
결국 모든 이동 경로에 대해서 dp에서 해당 경로에 대한 최소값을 넣어서 가지고 있다가 이 최솟값들의 합이 우측하단에 모이면 이것이 해당 위치로 오는 최단 경로의 개수가 될 것이다.
따라서 우측상단에서 가장 가까운 곳부터 최단 경로로 이동하기 위해 필요한 이동횟수를 넣으면서 이 횟수들을 가지고 다음 위치로 이동하는 횟수를 구하는 방법을 찾아야 한다. DP를 사용할 수 밖에 없다.
직접 미로를 그려서 최단거리수를 적어넣으면 어떻게 값을 만들어나가야할지 알수 있다.
간단하게 아래와 같이 된다.
0 0 0 0
0 1 0 0
0 1 0 0
0 1 0 0
먼저 열을 1로 고정해서 1번 열에다가 최단거리수 1을 채운다. 그다음
0 0 0 0
0 1 1 0
0 1 0 0
0 1 0 0
행을 1로 고정해서 최단거리수 1을 채운다.
이상태로 다음은 어떻게 채워야할까? 어느위치를 더하면서 i행 j열을 채워줘야할까?
이중 for문을 돌면서 i가 2부터 m까지, j가 2부터 n까지 돌아야될 것은 알 수 있다. 그래야 m,n의 위치까지 채울 수 있기 때문이다.
그리고 i,j를 구하기 위해 더해야할 조합은 [i-1][j]번 인덱스와 [i][j-1]번 인덱스다. 예를 들어, 이제 [2][2]번 위치를 채우려고 하면 [1][2]번 인덱스인 1과 [2][1]번 인덱스인 1을 더해서 2가 이 위치로 갈 수 있는 최단거리수가 된다.
0 0 0 0
0 1 1 0
0 1 2 0
0 1 0 0
여기서 마지막 [3][3] 위치를 채우려면 동일하게 [2][3]과 [3][2]의 값을 더하면 된다. 2와 1이다..
0 0 0 0
0 1 1 0
0 1 2 0
0 1 3 0
이렇게 완성이 된다.
입력이 m=1, n=1로 들어왔을 때는 이렇게 진행된다.
먼저 열을 1로 고정해서 최단거리수 1을 채운다.
0 0
0 1
그다음 행을 1로 고정해서 최단거리수 1을 채운다.
0 0
0 1
m, n이 1이므로 이중 for문은 돌지 않는다.
소스코드
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
const uniquePaths = function (m, n) {
const dp = [...Array(m > n ? m + 1 : n + 1)].fill(0).map(() => [...Array(m > n ? m + 1 : n + 1)].fill(0));
for (let i = 1; i <= m; ++i) dp[i][1] = 1;
for (let i = 1; i <= n; ++i) dp[1][i] = 1;
for (let i = 2; i <= m; ++i) {
for (let j = 2; j <= n; ++j) dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
return dp[m][n];
};
test('TC1', () => {
expect(uniquePaths(3, 7)).toStrictEqual(28);
});
test('TC2', () => {
expect(uniquePaths(3, 2)).toStrictEqual(3);
});
test('TC3', () => {
expect(uniquePaths(7, 3)).toStrictEqual(28);
});
test('TC4', () => {
expect(uniquePaths(3, 3)).toStrictEqual(6);
});
test('TC5', () => {
expect(uniquePaths(1, 1)).toStrictEqual(1);
});
JavaScript
복사
