n차 정사각 행렬이 주어지고, 행렬의 모든 원소는 서로 다르다고 가정해 봅시다. 이때 우리가 찾아야 할 것은 경로를 따라 이동할 때마다 값이 정확히 1씩 증가하는 조건을 만족하는 최장 경로입니다. 한 칸에서는 왼쪽, 오른쪽, 위, 아래 네 방향으로만 이동할 수 있습니다.
예를 들어 다음과 같은 행렬이 있다고 가정하겠습니다.
| 1 | 2 | 9 |
| 5 | 3 | 8 |
| 4 | 6 | 7 |
이 경우 출력 결과는 4입니다. 가장 긴 경로는 6→7→8→9이기 때문입니다.
문제 해결 접근 방식
이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다.
- 모든 셀에 대해 해당 셀에서 시작하는 최장 경로의 길이를 각각 계산합니다.
- 모든 셀의 최장 경로 값을 구한 뒤, 그중 최댓값을 반환합니다.
여기서 중요한 관찰 포인트는 이 접근 방식에 많은 수의 겹치는 부분 문제(overlapping sub-problems)가 존재한다는 것입니다. 따라서 이 문제는 동적 프로그래밍(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. 조회 테이블 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
코드 설명
getLongestPathLengthUtil 함수는 재귀적으로 현재 위치(i, j)에서 네 방향을 탐색하며, 인접한 셀의 값이 현재 값보다 정확히 1 클 때만 해당 방향으로 이동합니다. table 배열에는 각 셀에서 계산된 최장 경로 길이가 저장되며, 값이 -1(미계산 상태)인 경우에만 새로 계산하여 메모이제이션 효과를 얻습니다. 메인 함수인 getLongestPathLength는 모든 셀을 순회하며 결과의 최댓값을 구해 반환합니다. 이러한 DP 기반 접근 덕분에 단순 브루트포스 탐색 대비 시간 복잡도를 크게 줄일 수 있습니다.