C++에서 주어진 제약 조건이 있는 행렬에서 가장 긴 경로 찾기

차수가 n인 정사각형 행렬이 하나 있다고 가정합니다. 그것은 모든 독특한 요소를 가지고 있습니다. 따라서 경로를 따라 있는 모든 셀이 1의 차이로 증가하는 순서가 되도록 최대 길이 경로를 찾아야 합니다. 한 셀에서 네 방향으로 이동할 수 있습니다. 왼쪽, 오른쪽, 위쪽 및 아래쪽. 따라서 행렬이 다음과 같은 경우 -

따라서 출력은 4가 됩니다. 가장 긴 경로는 6→7→8→9

이 문제를 해결하기 위해 우리는 이 아이디어를 따를 것입니다. 모든 셀에서 시작하는 가장 긴 경로를 계산합니다. 모든 셀에 대해 가장 긴 경로를 얻으면 모든 가장 긴 경로의 최대값을 반환합니다.

이 접근 방식에서 한 가지 중요한 관찰은 겹치는 하위 문제가 많다는 것입니다. 따라서 이 문제는 동적 프로그래밍을 사용하여 해결할 수 있습니다. 여기에서 조회 테이블 dp[][]를 사용하여 문제가 이미 해결되었는지 여부를 확인합니다.

예시

#include <iostream>
#define n 3
using namespace std;
int getLongestPathLengthUtil(int i, int j, int matrix[n][n], int table[n][n]) {
   if (i < 0 || i >= n || j < 0 || j >= n)
   return 0;
   if (table[i][j] != -1)
      return table[i][j];
   int x = INT_MIN, y = INT_MIN, z = INT_MIN, w = INT_MIN;
   if (j < n - 1 && ((matrix[i][j] + 1) == matrix[i][j + 1]))
      x = 1 + getLongestPathLengthUtil(i, j + 1, matrix, table);
   if (j > 0 && (matrix[i][j] + 1 == matrix[i][j - 1]))
      y = 1 + getLongestPathLengthUtil(i, j - 1, matrix, table);
   if (i > 0 && (matrix[i][j] + 1 == matrix[i - 1][j]))
      z = 1 + getLongestPathLengthUtil(i - 1, j, matrix, table);
   if (i < n - 1 && (matrix[i][j] + 1 == matrix[i + 1][j]))
      w = 1 + getLongestPathLengthUtil(i + 1, j, matrix, table);
      return table[i][j] = max(x, max(y, max(z, max(w, 1))));
}
int getLongestPathLength(int matrix[n][n]) {
   int result = 1;
   int table[n][n];
   for(int i = 0; i < n; i++)
   for(int j = 0; j < n; j++)
   table[i][j] = -1;
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if (table[i][j] == -1)
         getLongestPathLengthUtil(i, j, matrix, table);
         result = max(result, table[i][j]);
      }
   }
   return result;
}
int main() {
   int mat[n][n] = { { 1, 2, 9 },
   { 5, 3, 8 },
   { 4, 6, 7 } };
   cout << "Length of the longest path is "<< getLongestPathLength(mat);
}

출력

Length of the longest path is 4