파이썬, 가장 큰 정사각형 넓이 구하기

 

파이썬, 가장 큰 정사각형 넓이 구하기

 

글. 오상문 sualchi@daum.net

 

# 가장 큰 정사각형 찾기

def solution1(board):
  DP = board    
  for lo in range(1,len(board)):      # low_size
    for co in range(1,len(board[0])): # col_size
      if board[lo][co] != 0:
        DP[lo][co] += min(DP[lo][co-1],DP[lo-1][co-1],DP[lo-1][co])
  answer = max([n for row in board for n in row])
  return answer**2    # 가장 큰 정사각형 면적

 

def solution2(board):
  for x in range(1,len(board[0])):
    for y in range(1,len(board)):
      if board[y][x] == 1:
        board[y][x] = min(board[y-1][x-1],board[y-1][x],board[y][x-1])+1
  answer = max([n for row in board for n in row])       
  return answer**2

#-----------------------------------------------------------

 

data = [[0,0,0,0,0,1],
       [1,1,1,1,1,1],
       [1,1,1,1,0,1],
       [1,1,1,1,1,1],
       [1,1,1,1,1,1]]

 

print(solution1(data))  # 16
print(solution1(data))  # 16

<이상>