JavaScript로 행렬에서 가장 긴 연속된 1의 줄 찾기

문제 소개

다음과 같이 0 또는 1만 포함하는 이진 행렬(배열의 배열)이 있다고 가정해 보겠습니다.

const arr = [
    [0,1,1,0],
    [0,1,1,0],
    [0,0,0,1]
];

이러한 행렬을 첫 번째이자 유일한 인수로 받아 처리하는 JavaScript 함수를 작성해야 합니다.

문제 설명

함수의 목표는 행렬에서 연속된 1로 이루어진 가장 긴 줄을 찾아, 그 줄에 포함된 1의 개수를 반환하는 것입니다. 줄의 방향은 다음 네 가지 중 어느 것이든 가능합니다.

• 수평(horizontal)
• 수직(vertical)
• 대각선(diagonal)
• 역대각선(anti-diagonal)

예를 들어 위 배열의 경우 출력 결과는 다음과 같습니다.

const output = 3

가장 긴 줄은 arr[0][1]에서 시작하여 대각선 방향으로 arr[2][3]까지 이어지는 줄이기 때문입니다.

arr[2][3]

접근 방식: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 각 셀(i, j)에 대해 네 가지 방향별로 현재 위치에서 끝나는 연속된 1의 개수를 저장하는 3차원 DP 배열을 생성합니다.

• dp[i][j][0] — 수평 방향(왼쪽 → 오른쪽)
• dp[i][j][1] — 수직 방향(위 → 아래)
• dp[i][j][2] — 대각선 방향(왼쪽 위 → 오른쪽 아래)
• dp[i][j][3] — 역대각선 방향(오른쪽 위 → 왼쪽 아래)

행렬을 순회하면서 값이 1인 셀을 만날 때마다 네 방향의 연속 개수를 갱신하고, 그중 최댓값을 결과값으로 유지합니다. 시간 복잡도는 O(rows × cols)로 매우 효율적입니다.

예제 코드

이를 구현한 코드는 다음과 같습니다.

const arr = [
    [0,1,1,0],
    [0,1,1,0],
    [0,0,0,1]
];
const longestLine = (arr = []) => {
    if(!arr.length){
        return 0;
    }
    let rows = arr.length, cols = arr[0].length;
    let res = 0;
    const dp = Array(rows).fill([]);
    dp.forEach((el, ind) => {
        dp[ind] = Array(cols).fill([]);
        dp[ind].forEach((undefined, subInd) => {
            dp[ind][subInd] = Array(4).fill(null);
        });
    });
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (arr[i][j] == 1) {
                dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
                dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
                dp[i][j][2] = (i > 0 && j > 0) ? dp[i - 1][j - 1][2] + 1 : 1;
                dp[i][j][3] = (i > 0 && j < cols - 1) ? dp[i - 1][j + 1][3] + 1 : 1;
                res = Math.max(res, Math.max(dp[i][j][0], dp[i][j][1]));
                res = Math.max(res, Math.max(dp[i][j][2], dp[i][j][3]));
            };
        };
    };
    return res;
};
console.log(longestLine(arr));

출력 결과

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

3