[leetcode][329] Longest Increasing Path in a Matrix

문제 : leetcode.com/problems/longest-increasing-path-in-a-matrix/

---

N*M 정수 배열이 주어질 때, 각 셸에서 상하좌우에 위치한 셸이며 현재 셸의 수보다 높은 수를 가지는 셸로 이동가능하다.

가장 긴 경로 길이를 구하라.

---

DFS + DP 로 풀었다.

i번째 셀에서 상하좌우로 이동가능한 곳으로 이동하면서 이동 가능한 경로의 최장 길이를 저장하는 배열(let, dp)을 만든다.

dp[i] = min(dp[상하좌우 중 이동가능한 곳])

위 점화식을 적용하며 dp배열을 dfs로 탐색하면서 세팅한다.

dp 배열이 이미 갱신된적 있다면 새로 값을 구하지 않고 해당 값을 사용하여 시간을 줄일 수 있다.

 

시간복잡도, 공간복잡도 모두 O(NM).

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/329.%20Longest%20Increasing%20Path%20in%20a%20Matrix.cpp