[프로그래머스] 가장 큰 정사각형 찾기 python (*)

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

출처 : 프로그래머스

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

---

코드

def solution(board):
    answer = 0
    row = len(board)
    col = len(board[0])

    for r in range(1,row):
        for c in range(1,col):
            if board[r][c] == 1:
                board[r][c] = min(board[r][c-1], board[r-1][c], board[r-1][c-1])+1
                answer = max(answer, board[r][c])
    for b in board:
        if max(b) > answer:
            answer = max(b)
        
    return answer**2

 

풀이

dp 문제이다.

현재 찾아야 하는 해는 최대 넓이의 정사각형이 될 수 있는 변의 길이다.

해를 구해 answer 에 넣고 **2 를 해서 넓이를 return 한다.

 

정사각형을 구할 때, board를 돌면서 1이면 정사각형이 가능하다.

하지만, 주변에도 1이 있어야 최대의 정사각형이 된다.

정사각형이 되려면? 현재 위치의 위, 왼쪽, 왼쪽 위 대각선 의 위치에도 1이 있어야 한다.

            if board[r][c] == 1:
                board[r][c] = min(board[r][c-1], board[r-1][c], board[r-1][c-1])+1

 

현재 위치의 위, 왼쪽, 왼쪽 위 대각선의 위치의 가장 작은 수의 +1 을 해주는 이유는

모두 같은 수라면 +1 해서 커질 것이고

하나라도 0이 있거나 작은 수가 있으면 정사각형은 작아질 것이다.