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

문제

 

---

풀이

격자 내부를 모두 탐색하는 방법을 사용하였다.

 

def canCal(x, y, r, c):
    if 0 <= x and x + c < m and 0 <= y and y + r < n:
        return True
    else:
        return False

격자를 탐색하기 위해 먼저 사각형이 격자 내부에 있는지 확인하는 함수를 만들었다.

시작 좌표와 가로, 세로의 추가 크기를 인자로 받고 해당 직사각형이 범위를 넘어가는지 확인한다.

 

def simul(x, y):
    global res
    for i in range(n):
        for j in range(m):
            if canCal(x, y, i, j):
                if cal(x, y, i, j):
                    res = max(res, (j+1) * (i+1))

실제 시뮬레이션을 진행하는 함수이다.

직사각형을 만들기 위해서 가로 세로를 순차적으로 1씩증가시키고, 만든 직사각형의 위치와 가로, 세로의 길이를 

canCal함수로 넣어 유효한 직사각형인지 체크한다.

그 뒤 cal함수를 이용해 직사각형이 양수만 포함하는지 확인 후 넓이를 계산한다.

 

for i in range(n):
    for j in range(m):
        simul(j, i)

print(res)

직사각형의 시작지점은 모든 좌표에 대해 가능하기 때문에

2중 for문을 사용하였다.

 

시뮬레이션 후 res값을 출력한다.

 

 

코드

n, m = map(int, input().split())

matrix = [list(map(int, input().split())) for _ in range(n)]
res = -1

def canCal(x, y, r, c):
    if 0 <= x and x + c < m and 0 <= y and y + r < n:
        return True
    else:
        return False

def cal(x, y, r, c):
    for i in range(c + 1):
        for j in range(r + 1):
            if matrix[y + j][x + i] <= 0:
                return False
    return True


def simul(x, y):
    global res
    for i in range(n):
        for j in range(m):
            if canCal(x, y, i, j):
                if cal(x, y, i, j):
                    res = max(res, (j+1) * (i+1))

for i in range(n):
    for j in range(m):
        simul(j, i)

print(res)