[코드트리] 양수 직사각형의 최대 크기 Python

직사각형 형성의 조건을 생각해보면 간단하게 해결할 수 있다.

대각선을 기준으로 시작점과 끝점을 잡으면 직사각형의 범위를 잡을 수 있다.

# n, m 입력
n, m = map(int, input().split())
# grid 입력
grid = [
    list(map(int, input().split()))
    for _ in range(n)
]

# 함수들
# is_plus(sx, sy, ex, ey)
def is_plus(sx, sy, ex, ey):
    # (sx, sy) 에서 (ex, ey)까지 탐색
    for i in range(sx, ex + 1):
        for j in range(sy, ey + 1):
            # 한번이라도 양수가 아니면
            if grid[i][j] <= 0:
                # 실패
                return False
    
    # 다돌았으면 성공
    return True

# get_max_size(x, y)
def get_max_size(x, y):
    
    # curr_max_size
    curr_max_size = -1

    # 완전 탐색 시작 -> 끝점
    for i in range(x, n):
        for j in range(y, m):
            # 시작점부터 끝점 내에 속한 모든 점이 양수라면
            if is_plus(x, y, i, j):
                # curr_size
                curr_size = (i - x + 1) * (j - y + 1)
                # curr_max_size update
                curr_max_size = max(curr_max_size, curr_size)
    
    # 반환
    return curr_max_size

# 설계
# max_size
max_size = -1

# 완전 탐색 시작 -> 시작점
for i in range(n):
    for j in range(m):
        # max_size update
        max_size = max(max_size, get_max_size(i, j))

# 출력
print(max_size)