JavaScript로 합이 가장 작은 경로 찾기

문제

숫자로 이루어진 2차원 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 각 행에서 정확히 하나의 요소를 선택해 경로를 구성하되, 인접한 두 행에서 선택한 요소는 서로 같은 열에 위치해서는 안 됩니다. 그런 다음 가능한 모든 경로 중에서 합이 가장 작은 경로의 합을 반환해야 합니다.

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

const arr = [
    [4, 7, 1],
    [2, 8, 3],
    [5, 6, 9]
]

이때 기대하는 출력 결과는 다음과 같습니다.

const output = 9;

출력 설명

배열에서 만들 수 있는 모든 유효한 경로는 다음과 같습니다.

이 중 [1, 2, 6] 경로의 합이 9로 가장 작으므로 정답은 9가 됩니다.

알고리즘 접근 방식

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 가장 아래쪽 행부터 위쪽으로 이동하면서, 각 열을 선택했을 때 만들 수 있는 최소 경로 합을 계산합니다.

여기서 핵심은 각 행마다 최소 합과 두 번째로 작은 합을 함께 추적하는 것입니다. 인접한 행에서는 같은 열을 선택할 수 없기 때문에, 현재 위치의 열이 바로 아래 행의 최소 합이 속한 열과 동일하다면 두 번째로 작은 합을 대신 사용해야 하기 때문입니다. 이 방식을 사용하면 모든 경로를 일일이 탐색하는 브루트 포스 방식보다 훨씬 효율적인 O(n × m) 시간 복잡도로 문제를 해결할 수 있습니다.

예제 코드

위 접근 방식을 구현한 코드는 다음과 같습니다.

const arr = [
    [4, 7, 1],
    [2, 8, 3],
    [5, 6, 9]
]
const minimumPathSum = (arr = []) => {
    let first = [0, null];
    let second = [0, null];
    for(let row = arr.length - 1; row >= 0; row--){
        let curr1 = null;
        let curr2 = null;
        for(let column = 0; column < arr[row].length; column++){
            let currentSum = arr[row][column];
            if(column !== first[1]){
                currentSum += first[0];
            }else{
                currentSum += second[0];
            };
            if(curr1 === null || currentSum < curr1[0]){
                curr2 = curr1;
                curr1 = [currentSum, column];
            }else if(curr2 === null || currentSum < curr2[0]){
                curr2 = [currentSum, column];
            };
        };
        first = curr1;
        second = curr2;
    };
    return first[0];
};
console.log(minimumPathSum(arr));

출력

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

9