[programmers] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905#

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

• 이 문제는 완전 탐색으로 풀 수도 있겠지만, 시간 초과를 피하기는 쉽지 않을 것 같습니다. 1000 * 1000 조건에다가 중복되는 연산들이 많기 때문이죠.
• 중복되는 연산이 있다? 그렇다면 생각해볼 수 있는게 다이나믹 프로그래밍(DP)이였습니다. 어쨌든 3 * 3 정사각형이 만들어지기 위해서는 2 * 2 정사각형이 만들어져야 가능했으니까요.
• DP로 생각해보면, 먼저 현재 위치가 [i][j]라고 했을 때, [i-1][j], [i][j-1], [i-1][j-1] 에 있는 원소들을 파악해서 가장 작은 원소를 Min에 넣어두고, 가장 작은 원소에 + 1 한 값을 현재 위치인 [i][j]에 담아줍니다. 이렇게 되면 현재 위치인 [i][j]에 담기는 값은 [i][j]에서 만들 수 있는 가장 큰 정사각형을 만든 셈인 것이죠.
• 이후에 for문을 돌면서 [i][j] 값들 중 가장 큰 값을 찾으면 그 값이 바로 정사각형 한 변의 길이가 될것이고, 제곱(^2)을 해주면 정사각형의 넓이가 나오겠죠?
• 두 가지 주의 할 사항은 모두 0일 경우와, [[0, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0]] 이런 식으로 직사각형이 가능한 정사각형일 경우를 고려해줘야 합니다.
• 자세한 설명은 주석을 참고해주시면 감사하겠습니다.

def solution(board):
    Max = 0
    n = len(board)
    m = len(board[0])
    flag = 0
    #모든 요소가 0인경우를 체크해준다.
    for b in board: 
        flag += b.count(0)
    if flag == n*m:
        return 0
    # 2중 for문으로 dp 테이블을 완성시킨다.
    for i in range(1,n):
        for j in range(1,m):
            if board[i][j] == 0:
                continue
            else:
                Min = min(board[i-1][j-1],board[i-1][j],board[i][j-1])
                board[i][j] = Min + 1
                Max = max(Max,board[i][j])
    # Max가 0 이라는 건 크기가 1인 정사각형을 고려해줘야 한다는 것이다.
    if Max == 0:
        return 1
    else:
        # 제곱을 해서 넓이를 구해준다.
        return Max ** 2