[leetcode][63] Unique Paths II

문제 : https://leetcode.com/problems/unique-paths-ii/description/

---

 

로봇이 M x N 그리드의 왼쪽 위 코너에 있다. 로봇은 아래나 오른쪽으로만 움직일 수 있다.

그리드에는 장애물들이 있다. 장애물이 있는 경우 해당 칸으로는 갈 수 없다.

로봇이 그리드의 오른쪽 아래 코너로 가려고 할때 경우의 수는 총 몇 가지인가.

---

2차원 배열을 만든다.

d[i][j] = (i, j)에서 도착점까지 갈 수 있는 경우의 수.

위 배열을 채우면 되는데, 로봇이 이동할 수 있는 방향은 아래, 오른쪽이고 장애물은 이동할 수 없다는 것으로 점화식을 세울 수 있다.

d[i][j] = d[i+1][j] + d[i][j+1] ((i, j)가 장애물이 아닌 경우)
d[i][j] = 0 ((i, j)가 장애물인 경우)

주어진 조건으로 점화식을 만들면 위와 같다.

(i, j)가 그리드의 오른쪽 아래 코너라면 1이 세팅된다. (오른쪽 아래 코너가 도착지이기 때문)

모든 배열을 채우며 d[0][0]을 구하면 해당 값이 정답이된다.

 

시간복잡도는 O(NM)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/63.%20Unique%20Paths%20II.cpp