파이썬에서 재배열로 가장 큰 부분행렬을 찾는 프로그램

m x n 이진 행렬이 있다고 가정하면 행렬의 열을 임의의 순서로 재배열할 수 있습니다. 재정렬 작업을 수행한 후 부분행렬의 모든 요소가 1인 행렬 내에서 가장 큰 부분행렬의 면적을 찾아야 합니다.

따라서 입력이 다음과 같으면

그러면 출력은 4가 됩니다. 열 스와핑 후에는

여기서 최대 부분행렬은 4개의 1이 있는 정사각형 크기입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• row :=행렬의 행 수, col :=행렬의 열 수
• 0에서 col - 1까지의 범위에 있는 j에 대해
  • 1~1행 범위의 i에 대해
    • 행렬[i, j]가 1이면
      • 행렬[i, j] :=행렬[i, j] + 행렬[i-1, j]
• ans :=0
• 0~1행 범위의 i에 대해
  • 목록 행렬 정렬[i]
  • col-1에서 0 사이의 j에 대해 1만큼 감소, do
    • 행렬[i, j]이 0과 같으면
      • 루프에서 나오다
      • ans =ans 및 (col-j)*matrix[i, j])의 최대값
• 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(matrix):
   row, col = len(matrix), len(matrix[0])
   for j in range(col):
      for i in range(1,row):
         if matrix[i][j]:
            matrix[i][j]+=matrix[i-1][j]
   ans = 0
   for i in range(row):
      matrix[i].sort()
      for j in range(col-1,-1,-1):
         if matrix[i][j]==0:
            break
         ans = max(ans, (col-j)*matrix[i][j])
   return ans

matrix = [[0,0,1],[1,1,1],[1,0,1]]
print(solve(matrix))

입력

[[0,0,1],[1,1,1],[1,0,1]]

출력

4