<Hard> Longest Increasing Path in a Matrix (LeetCode : C#)

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

📕 문제 설명

matrix에서 증가하는 구간이 가장 긴 path의 길이 반환하기 (대각선이나 경계 밖으로 움직이는 것은 불가능)

• Input
  matrix 정보
• Output
  증가하는 구간이 가장 긴 path의 길이

예제

시도 1.

완전 탐색으로 DFS 재귀 돌려서 모든 케이스 확인하기 (시간 초과)

public class Solution {
    public int LongestIncreasingPath(int[][] matrix) {
        int answer = 0;
        int[] x = new int[4] {1, -1, 0, 0};
        int[] y = new int[4] {0, 0, 1, -1};
        for (int i = 0; i < matrix.Length; i++)
        {
            for (int j = 0; j < matrix[0].Length; j++)
            {
                answer = Math.Max(answer, DFS(i, j, 1));
            }
        }

        return answer;

        int DFS(int currX, int currY, int currLength)
        {
            int maxLength = 0;
            for (int i = 0; i < 4; i++)
            {
                int newX = currX + x[i];
                int newY = currY + y[i];

                if (newX < 0 || newX >= matrix.Length || newY < 0 || newY >= matrix[0].Length) continue;

                if (matrix[currX][currY] < matrix[newX][newY])
                {
                    maxLength = Math.Max(maxLength, DFS(newX, newY, currLength + 1));
                }
            }

            return Math.Max(maxLength, currLength);
        }
        
    }


}

풀이

memo 사용해서 풀었다. 결국 이전에 봤던 값들을 해당 칸에서 maxLength처럼 기록할 수 있기 때문에 정보들 저장해두고 방문했으면 재귀 더 안돌고 그 값 가져오게끔

public class Solution {
    public int LongestIncreasingPath(int[][] matrix) {
        int answer = 0;
        int[] x = new int[4] {1, -1, 0, 0};
        int[] y = new int[4] {0, 0, 1, -1};

        int[,] maxLength = new int[matrix.Length, matrix[0].Length];

        for (int i = 0; i < matrix.Length; i++)
        {
            for (int j = 0; j < matrix[0].Length; j++)
            {
                answer = Math.Max(answer, DFS(i, j));
            }
        }

        return answer;

        int DFS(int currX, int currY)
        {
            if (maxLength[currX, currY] != 0) return maxLength[currX, currY];

            for (int i = 0; i < 4; i++)
            {
                int newX = currX + x[i];
                int newY = currY + y[i];

                if (newX >= 0 && newX < matrix.Length && newY >= 0 && newY < matrix[0].Length && matrix[currX][currY] < matrix[newX][newY])
                {
                    maxLength[currX, currY] = Math.Max(maxLength[currX, currY], DFS(newX, newY));
                }
            }

            return ++maxLength[currX, currY]; // 자기 자신 추가하기
        }
        
    }


}

결과