Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구하는 이진 행렬에서 가장 긴 연속된 1의 라인

문제 소개

0과 1로만 구성된 이진 행렬(binary matrix) M이 주어졌을 때, 행렬 안에서 연속된 1로 이루어진 가장 긴 라인의 길이를 찾는 문제입니다. 이때 라인은 가로(수평), 세로(수직), 대각선, 반대 대각선 네 방향 중 어느 것이든 가능합니다.

예를 들어 입력이 다음과 같다면,

0110
0110
0001

정답은 3이 됩니다. 두 번째 열에 세로 방향으로 연속된 세 개의 1이 존재하기 때문입니다.

해결 전략: 동적 계획법(DP)

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 칸마다 네 방향별로 "해당 칸에서 끝나는 연속된 1의 길이"를 저장하는 것입니다.

  • ret := 0 으로 결과값을 초기화합니다.

  • n := M의 행 개수, m := M의 열 개수로 설정합니다.

  • 크기가 n × m × 4인 3차원 배열 dp를 정의합니다. 인덱스 0은 세로, 1은 가로, 2는 대각선, 3은 반대 대각선 방향을 의미합니다.

  • 첫 번째 행을 초기화합니다. i := 0부터 i < m까지 반복하며, j := 0부터 j < 4까지 반복해서 다음을 수행합니다.

    • dp[0][i][j] := M[0][i]

    • ret := max(ret, dp[0][i][j]) 로 갱신

  • 첫 번째 행의 가로 방향을 처리합니다. j := 0부터 j < m까지 반복하면서, M[0][j]가 0이 아니고 j > 0이라면 다음을 수행합니다.

    • dp[0][j][1] := 1 + dp[0][j - 1][1]

    • ret := max(ret, dp[0][j][1]) 로 갱신

  • 나머지 행들을 순회합니다. i := 1부터 i < n까지, 그리고 각 행에서 j := 0부터 j < m까지 반복하며 다음을 수행합니다.

    • dp[i][j][0] := (M[i][j]가 0이 아니면 1 + dp[i - 1][j][0], 그렇지 않으면 0)

    • j > 0인 경우:

      • dp[i][j][1] := (M[i][j]가 0이 아니면 dp[i][j - 1][1] + 1, 아니면 0)

      • dp[i][j][2] := (M[i][j]가 0이 아니면 dp[i - 1][j - 1][2] + 1, 아니면 0)

    • 그렇지 않으면:

      • dp[i][j][1] := M[i][j]

      • dp[i][j][2] := M[i][j]

    • j + 1 < m인 경우:

      • dp[i][j][3] := (M[i][j]가 0이 아니면 dp[i - 1][j + 1][3] + 1, 아니면 0)

    • 그렇지 않으면:

      • dp[i][j][3] := M[i][j]

    • k := 0부터 k < 4까지 반복하며 ret := max(ret, dp[i][j][k]) 로 갱신합니다.

  • 모든 순회가 끝나면 ret을 반환합니다.

이 방법의 시간 복잡도는 O(n × m), 공간 복잡도 역시 O(n × m)입니다. 모든 칸을 한 번씩만 방문하면서 네 방향의 정보를 동시에 누적하기 때문에 매우 효율적입니다.

C++ 구현 예시

아래 구현을 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int longestLine(vector<vector<int>>& M) {
      int ret = 0;
      int n = M.size();
      int m = !n ? 0 : M[0].size();
      vector<vector<vector<int> > > dp(n, vector<vector<int> >(m, vector<int>(4)));
      for (int i = 0; i < m; i++) {
         for (int j = 0; j < 4; j++) {
            dp[0][i][j] = M[0][i];
            ret = max(ret, dp[0][i][j]);
         }
      }
      for (int j = 0; j < m; j++) {
         if (M[0][j] && j > 0) {
            dp[0][j][1] = 1 + dp[0][j - 1][1];
            ret = max(ret, dp[0][j][1]);
         }
      }
      for (int i = 1; i < n; i++) {
         for (int j = 0; j < m; j++) {
            dp[i][j][0] = M[i][j] ? 1 + dp[i - 1][j][0] : 0;
            if (j > 0) {
               dp[i][j][1] = M[i][j] ? dp[i][j - 1][1] + 1 : 0;
               dp[i][j][2] = M[i][j] ? dp[i - 1][j - 1][2] + 1 : 0;
            }
            else {
               dp[i][j][1] = M[i][j];
               dp[i][j][2] = M[i][j];
            }
            if (j + 1 < m) {
               dp[i][j][3] = M[i][j] ? dp[i - 1][j + 1][3] + 1 : 0;
            }
            else {
               dp[i][j][3] = M[i][j];
            }
            for (int k = 0; k < 4; k++) {
               ret = max(ret, dp[i][j][k]);
            }
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1,1,0},{0,1,1,0},{0,0,0,1}};
   cout << (ob.longestLine(v));
}

입력

{{0,1,1,0},{0,1,1,0},{0,0,0,1}}

출력

3