문제

0 과 1로 이루어진 2차원 배열에서 1 로 이루어진 가장 큰 정사각형을 찾아 넓이를 리턴하는 문제이다.
ex)

square
return: 3

접근법

처음에는 이중 for문을 돌아 일일이 다 확인하려 했으나 시간초과..
애초에 정사각형 내부가 모두 1인지 확인하려면 2중 for문을 돌아야하는데 이러면 무조건 시간초과가 뜬다. 여러 삽질을 하다가 결국 생각해내지 못하고 다른사람의 풀이를 참고했다.

side = 0

최초의 정사각형의 한변의 길이를 side 라 하고 값을 0 이라 하자.

d 의 값이 1인 모든 2x2 행렬에서
a, b, c 의 최솟값 + 1 과 side 값 중 큰 값을 side 값으로 바꾸고
side 값은 d에 들어간다. 이렇게 모두 순회하면 side 값은 가장 큰 정사각형의 한변의 길이가 나온다.

side = max(min(a,b,c)+1, side)
d = side

code

def solution(board):
    side = 0
    flag = 0
    for i in range(len(board)):
        if 1 in board[i][:]:
            flag = 1
    if flag == 0:
        return 0

    else:
        for i in range(1, len(board)):
            for j in range(1, len(board[i])):
                if board[i][j] == 1:
                    square = []
                    square.append(board[i-1][j])
                    square.append(board[i][j-1])
                    square.append(board[i-1][j-1])
                    board[i][j] = min(square) + 1
                    side = max(min(square)+1, side)
        if side == 0:
            return 1
        return side ** 2