2304. Minimum Path Cost in a Grid

2304. Minimum Path Cost in a Grid

https://leetcode.com/problems/minimum-path-cost-in-a-grid/

문제

이 문제는 최단거리와 최단거리를 지나는 노드들에 합을 구하는 문제이다.
이해하기 힘든 문제였기에 문제를 설명을 해보자면 첫 번째 노드 5가 갈 수 있는 노드는 노드 4, 노드 0이 있다. 여기서 비용을 구해야 하는데 moveCost[5]인 값을 찾으면 된다. 따라서 5 -> 4로 가는 비용은 14가 되고 5 -> 0로 가는 비용은 3이 된다. 이러한 방법으로 그림을 그리게 되면 Example 1과 같은 그림이 나오게 된다.

풀이

잘 알고 있는 DFS 그림이 나온다. 깊이 우선 탐색으로 모든 경우의 수를 계산함과 동시에 현재 노드에 자식노드들 중 최소비용과 해당 노드를 더한값을 리턴하면 어떨까라는 생각을 하게 되었다.

여기서 중요한 사실이 Recursive한 방법이기 때문에 이미 구한 값을 계속해서 구할 수도 있다.
이러한 문제를 해결하기 위해서 cache최적화 방법을 사용하였고 이미 구했다면 계속해서 재귀함수를 호출하지 않고 캐시값에서 리턴하여 최적화하였다. 캐시를 사용하지 않으면 TLE가 발생하지만 캐시값을 사용하여 해결하였다.

결과

배운점

1. DP문제를 풀 때 모든 경우에 수를 구해야 할 것 같으면 DFS를 생각하자.
2. DFS를 사용할 때 무조건 불필요한 연산을 할 수 있으니 cache를 생각하자.
3. 문제를 해결하는데 많은 시간이 걸렸다. 많이 연습하자!