이진 행렬이 있다고 가정하고 주어진 행렬에서 1의 가장 큰 제곱을 찾아야 합니다.
따라서 입력이 다음과 같으면
1 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 |
그러면 출력은 16이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- res :=0
- 행렬 크기 범위 0에서 i에 대해
- res :=res 및 matrix[i, 0]의 최대값
- 행렬 [0]의 크기 범위 0에 있는 i에 대해
- res :=res 및 matrix[0, i]의 최대값
- 행렬의 행 수까지 범위 1에 있는 i에 대해 다음을 수행합니다.
- 행렬의 열 개수에 대한 범위 1의 j에 대해 다음을 수행합니다.
- 행렬[i,j]가 1과 같으면
- 행렬[i, j] =(행렬[i - 1, j], 행렬[i - 1, j - 1] 및 행렬[i, j - 1]) + 1의 최소값
- res =res 및 행렬[i, j]의 최대값
- 행렬[i,j]가 1과 같으면
- 행렬의 열 개수에 대한 범위 1의 j에 대해 다음을 수행합니다.
- 반환 결과^2
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, matrix): res = 0 for i in range(len(matrix)): res = max(res, matrix[i][0]) for i in range(len(matrix[0])): res = max(res, matrix[0][i]) for i in range(1, len(matrix)): for j in range(1, len(matrix[0])): if matrix[i][j] == 1: matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1 res = max(res, matrix[i][j]) return res * res ob = Solution() matrix = [ [1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 1], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0] ] print(ob.solve(matrix))
입력
matrix = [ [1, 0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1, 1], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0] ]
출력
16