백준(3321) - 가장 큰 직사각형 Python

백준(3321) - 가장 큰 직사각형

문제풀이: 그래프, 파이썬

해결방법

예시)

10 6
001010
111110
011110
111110
011110
111111
110111
110111
000101
010101

• 연속된 1을 기록한다.

  

• 각 행을 내림차순 정렬한다.

  

• 내림차순으로 정렬된 행들마다 직사각형의 넓이를 계산해준다.

  각 행렬에 적혀있는 값은 세로 길이라고 보면 되고,

  가로 길이는 1,2,3… 으로 하나씩 계산해가며 넓이의 최대값을 갱신해주면 된다.

import sys

N, M = map(int, input().split())
graph = [[] for _ in range(N)]

for i in range(N):
    input_data = sys.stdin.readline().rstrip()
    graph[i] = [int(i) for i in input_data]

for i in range(1, N):
    for j in range(M):
        if graph[i][j] == 1:
            graph[i][j] = graph[i-1][j] + 1

max_size = 0
for i in range(N):
    arr = graph[i]
    arr.sort(reverse=True)
    for idx in range(M):
        size = (idx+1) * arr[idx]
        max_size = size if size > max_size else max_size

print(max_size)