JavaScript로 2차원 배열에서 가장 긴 증가 경로 찾기

증가 수열이란?

증가 수열(Increasing Sequence)은 각 원소가 바로 앞의 원소보다 크거나 같은 숫자들의 나열을 의미합니다.

예를 들면 다음과 같습니다.

4, 6, 8, 9, 11, 14 → 증가 수열
3, 3, 3, 3, 3, 3, 3 → 역시 증가 수열

문제 정의

숫자로 이루어진 2차원 배열 arr을 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열 안에서 상하좌우로 이동하며 만들 수 있는 경로 중, 값이 계속 증가하기만 하는 가장 긴 경로의 길이를 찾아 반환해야 합니다.

예를 들어 함수에 다음과 같은 입력이 주어졌다고 가정해 보겠습니다.

const arr = [
    [4, 5, 6],
    [4, 3, 7],
    [3, 3, 2]
];

이때 기대되는 출력은 다음과 같습니다.

const output = 4;

출력 설명

가장 긴 증가 경로가 4 → 5 → 6 → 7이기 때문입니다. 이 경로는 왼쪽 위 모서리의 4에서 시작해 오른쪽으로 이동하며 값을 따라가고, 마지막에 아래 행의 7로 내려가며 총 길이 4를 만족합니다.

구현 예제

이 문제를 해결하는 코드는 다음과 같습니다.

const arr = [
    [4, 5, 6],
    [4, 3, 7],
    [3, 3, 2]
];
const longestIncreasingPath = (arr = []) => {
    let longest = 0;
    let dp = Array(arr.length).fill(null).map(() =>
    Array(arr[0].length).fill(1));
    const backtracking = (row, col) => {
        if (dp[row][col] !== 1) return dp[row][col];
        let dRow = [1,0,-1,0];
        let dCol = [0,1,0,-1];
        for (let i = 0; i < dRow.length; i++) {
            let nR = row + dRow[i], nC = col + dCol[i];
            if (nR >= 0 && nR < arr.length && nC >= 0 && nC < arr[0].length && arr[nR][nC] > arr[row][col]) {
                dp[row][col] = Math.max(dp[row][col], 1 + backtracking(nR, nC));
            }
        }
        return dp[row][col];
    }
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr[0].length; j++) {
            longest = Math.max(longest, backtracking(i, j));
        }
    }
    return longest;
};
console.log(longestIncreasingPath(arr));

코드 설명

핵심 아이디어

백트래킹(Backtracking) 기법과 깊이 우선 탐색(DFS)을 함께 활용합니다.
재귀 함수는 특정 행(row)과 열(col)에서 출발했을 때 만들 수 있는 가장 긴 증가 경로의 길이를 반환합니다.
dp 배열을 이용한 메모이제이션(Memoization)으로 이미 계산된 위치의 결과를 저장하고, 동일한 위치를 다시 방문할 경우 재계산 없이 저장된 값을 즉시 반환하여 중복 연산을 제거합니다.
배열의 모든 칸을 시작점으로 삼아 최장 경로를 계산한 뒤, 그중 가장 큰 값을 최종 결과로 반환합니다.

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.