Longest Increasing Path in a Matrix

리트코드 추천으로 처음 접하게 된 문제이다. 난이도가 Hard 여서 상당히 걱정을 하고 문제를 읽게 됐는데 생각보다 할만해 보였고 Memoization 을 이용한 DP 방식으로 쉽게 풀수있을거라고 생각했다.

Matrix가 주어졌을때 각 원소를 탐색하면서 원소가 커지는 가장 긴 구간을 리턴하면 된다. 그리고 여기서 DP를 생각할수밖에 없었던 이유중 하나는 만약에 DP와 같은 Memoization 방식을 사용 안한다면 정말 무수히 많은 구간을 중복으로 탐색 했을거다. 그리고 Matrix의 크기가 200 * 200 이라고 생각했을때 일반적인 DFS 방식으로는 안됐을거다.

내가 생각했던 이상적인 DP와 DFS를 활용한 방법이었다. 각 원소에서 이미 계산한 가장 긴 구간을 DP에 저장한 뒤에 원소를 모두 탐색하면서 가장 긴 구간을 리턴했다. 여기서 내가 좀 실수했다고 느끼는 점은 Visited 벡터가 필요할거라고 생각했던것이다. 생각해보면 각 원소를 하나하나 탐색할건데 visited 가 필요없었고 그거때매 오답이 좀 나왔었다.

개인적으로 조금 깔끔하다고 생각했던 다른 사람의 답중 하나였는데 나처럼 i+1...j+1 이런식으로 하지않고 그냥 dirs 벡터를 하나 만든게 좀 인상적이었다. 이런 방법도 나중에 문제를 풀때 고민해봐야겠다.

배운점:
1. Memoization 을 Matrix에 적용하기
2. 중복되는 구간 계산 생각하기