[코드트리/INTERMEDIATE LOW] Simulation 양수 직사각형 최대 크기 Python

 

 

🔥 문제 링크

https://www.codetree.ai/missions/2/problems/max-area-of-positive-rectangle?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

 

 

 

🔥 문제

 

 

 

🔥 풀이

✅ 직사각형의 시작점, 끝점을 정해서 해당 크기의 사각형 내에 있는 숫자들이 양수인지 판별하는 함수 필요

def isTrueSquare(sx, sy, ex, ey): #start x, start y, end x, end y

	# 시작점부터 끝점까지 완전탐색
    for i in range(sx, ex+1):
        for j in range(sy, ey+1):
        	
            #한 좌표라도 음수가 나오면 False
            if ground[i][j] <= 0:
                return False
                
    #전부 양수라면 True 반환
    return True

 

✅ 위 함수를 이용해서 양수로 이루어진 직사각형의 양끝점 파악 후 크기 구함 -> 직사각형 크기 최대값 갱신

    ✔️  abs 절대값 +1

    ✔️ 끝점의 좌표 - 시작점의 좌표 + 1

#사각형 크기
def max_squre(x, y):

    #최대 사각형 크기
    #양수로만 이루어진 직사각형이 없다면 -1 출력해야 하기 때문에 초기값 -1로 설정
    max_square_size = -1
    
    #현재 좌표부터 입력된 영역 끝까지 양수로 이루어진 가장 큰 직사각형 탐색
    for i in range(x, n):
        for j in range(y, m):
            if isTrueSquare(x, y, i, j):
                size = (i - x + 1) * ( j - y + 1)
                max_square_size = max(size, max_square_size)
    
    return max_square_size

 

⚠️ 양수로 이루어진 직사각형이 없을 경우 -1을 출력해야 함을 주의해야 함 (처음에 문제 제대로 읽지 않아 0으로 초기화할 뻔 했음...)

 

 

 

🔥 코드

def isTrueSquare(sx, sy, ex, ey): #start x, start y, end x, end y

	# 시작점부터 끝점까지 완전탐색
    for i in range(sx, ex+1):
        for j in range(sy, ey+1):
        	
            #한 좌표라도 음수가 나오면 False
            if ground[i][j] <= 0:
                return False
                
    #전부 양수라면 True 반환
    return True

#사각형 크기
def max_squre(x, y):

    #최대 사각형 크기
    #양수로만 이루어진 직사각형이 없다면 -1 출력해야 하기 때문에 초기값 -1로 설정
    max_square_size = -1
    
    #현재 좌표부터 입력된 영역 끝까지 양수로 이루어진 가장 큰 직사각형 탐색
    for i in range(x, n):
        for j in range(y, m):
            if isTrueSquare(x, y, i, j):
                size = (i - x + 1) * ( j - y + 1)
                max_square_size = max(size, max_square_size)
    
    return max_square_size


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

ground = [list(map(int, input().split())) for _ in range(n)]

max_size = -1

for i in range(n):
    for j in range(m):
        max_size = max(max_size, max_squre(i, j))

print(max_size)