[leetcode][1219] Path with Maximum Gold

문제 : https://leetcode.com/problems/path-with-maximum-gold/

---

grid 사이즈 조건이 n, m <= 15 이기 때문에 grid[x][y]가 0이 아닌 경우 그 지점을 시작점으로 DFS를 돌렸다.

DFS를 돌리면서 방문했던 지점은 다시 방문하면 안되므로 grid 값을 0으로 세팅해줬다.

DFS를 돌리면서 이때까지 들렸던 경로의 합이 최대가 되는 경우 정답이 된다.

 

시간복잡도는 특정 지점을 시작점으로 DFS를 돌릴 때 (NM)^2가 소요되고 0이아닌 지점을 시작점으로 하므로 NM 번 반복한다. 즉 총 시간복잡도는 O((NM)^3)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/1219.%20Path%20with%20Maximum%20Gold.cpp