[Leetcode] 980. Unique Paths III

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

---

m x n 정수형 배열 grid가 주어진다.

1 : 시작 지점. (1개 존재)

2 : 종료 지점. (1개 존재)

0 : 걸을 수 있는 곳

-1 : 장애물

 

상하좌우 4방향으로 이동가능할 때, 시작지점에서 종료지점으로 갈 수 있는 방법의 수를 구하라.

---

백트래킹.

시작지점부터 장애물이 아닌 곳으로 이동하면서 이동횟수를 저장하면서 상하좌우 방향으로 탐색한다.

탐색하면서 지나간 자리는 다시 못 지나가게 별도의 플래그 배열에 탐색한 위치는 표시를 해둔다.

종료지점에 도달했을 때, 걸음의 수가 grid 배열의 0, 2 cell의 수와 같다면 정답이 가능하므로 정답 방법의 수에 1을 더한다.

 

시간복잡도는..?

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/980.%20Unique%20Paths%20III.cpp